\u65f6\u95f4\u9650\u5236\uff1a1000MS \u00a0\u00a0\u00a0\u00a0 \u5185\u5b58\u9650\u5236\uff1a524288KB<\/p>\n
\u51fa\u9898\u4eba\uff1a \u7ed9\u5b9a\u5b57\u7b26\u4e32 \\(s\\) \u3002\u4f60\u9700\u8981\u56de\u7b54 \\(n\\) \u4e2a\u8be2\u95ee\uff0c\u7b2c \\(i\\) \u4e2a\u8be2\u95ee\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570 \\(k_i\\) \u548c\u4e00\u4e2a\u5b57\u7b26\u4e32 \\(m_i\\)\uff0c\u8bf7\u6c42\u51fa \\(s\\) \u7684\u6240\u6709\u5b50\u4e32 \\(t\\) \u4e2d\uff0c\u6ee1\u8db3 \\(m_i\\) \u5728 \\(t\\) \u4e2d\u51fa\u73b0\u81f3\u5c11 \\(k_i\\) \u6b21\u7684\u5b57\u7b26\u4e32 \\(t\\) \u7684\u957f\u5ea6\u7684\u6700\u5c0f\u503c\u3002<\/p>\n \u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\u5b50\u4e32\u662f\u8be5\u5b57\u7b26\u4e32\u4e2d\u7684\u8fde\u7eed\u4e00\u6bb5\u5b57\u7b26\u3002<\/p>\n \u4fdd\u8bc1\u4efb\u610f\u4e24\u4e2a\u8be2\u95ee\u7684 \\(m_i\\) \u4e0d\u76f8\u540c\u3002<\/p>\n \u7b2c\u4e00\u884c\u5305\u542b\u4e00\u4e2a\u5b57\u7b26\u4e32 \\(s\\)\uff08\\(1 \\leq \\left|s\\right| \\leq 10^5\\)\uff09\u3002<\/p>\n \u7b2c\u4e8c\u884c\u5305\u542b\u4e00\u4e2a\u6b63\u6574\u6570 \\(n\\)\uff08\\(1 \\leq n \\leq 10^5\\)\uff09\u3002<\/p>\n \u63a5\u4e0b\u6765 \\(n\\) \u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u6b63\u6574\u6570 \\(k_i\\)\uff08\\(1 \\leq k_i \\leq \\left|s\\right|\\)\uff09\u548c\u4e00\u4e2a\u975e\u7a7a\u5b57\u7b26\u4e32 \\(m_i\\)\uff0c\u8868\u793a\u7b2c \\(i\\) \u4e2a\u8be2\u95ee\u3002<\/p>\n \u6240\u6709\u5b57\u7b26\u4e32\u4ec5\u5305\u542b\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\uff0c\u4e14\u6240\u6709\u8be2\u95ee\u5b57\u7b26\u4e32\u7684\u603b\u957f\u5ea6\u4e0d\u8d85\u8fc7 \\(10^5\\) \u3002<\/p>\n \u5bf9\u4e8e\u6bcf\u4e2a\u5b57\u7b26\u4e32\u8f93\u51fa\u4e00\u884c\u8868\u793a\u7b54\u6848\u3002<\/p>\n \u5982\u679c \\(m_i\\) \u5728 \\(s\\) \u4e2d\u51fa\u73b0\u6b21\u6570\u5c0f\u4e8e \\(k_i\\)\uff0c\u8f93\u51fa \\(-1\\) \u3002<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n \u9898\u89e3\u7684\u505a\u6cd5\uff1a<\/p>\n \u5c06\u6240\u6709\u7684\u5339\u914d\u4e32\u5efa\u4e00\u4e2a AC\u81ea\u52a8\u673a\uff0c\u7136\u540e\u6bcd\u4e32\u653e\u5728\u4e0a\u9762\u8dd1\uff0c\u7ecf\u8fc7\u7684\u70b9\u8ba1\u5165\u4e0b\u5f53\u524d\u6bcd\u4e32\u6240\u5339\u914d\u5230\u7684\u4f4d\u7f6e\uff0c\u7528 \u8bc1\u660e\u8be5\u7b97\u6cd5\u603b\u590d\u6742\u5ea6\u662f \\(O(nlog^2n+n\\sqrt n)\\)<\/p>\n \u590d\u6742\u5ea6\u7684\u5173\u952e\u5728\u4e8e\u8bc1\u660e \u6240\u6709\u5339\u914d\u4e32\u5728\u6bcd\u4e32\u51fa\u73b0\u6b21\u6570\u4e4b\u548c \u8303\u56f4\u6709\u4fdd\u8bc1\u3002<\/p>\n \u9898\u76ee\u4e2d\u4fdd\u8bc1\u4efb\u610f\u7684\u4e32 \\(m_i\\) \u5747\u4e0d\u76f8\u540c\uff0c\u6240\u4ee5\u957f\u5ea6\u5927\u4e8e \\(\\sqrt n\\) \u6700\u591a\u53ea\u80fd\u51fa\u73b0 \\(\\sqrt n\\) \u6b21\uff0c\u957f\u5ea6\u5c0f\u4e8e \\(\\sqrt n\\) \u7684 \\(s\\) \u7684\u5b50\u4e32\u5728\u6bcd\u4e32\u51fa\u73b0\u6b21\u6570\u4e4b\u548c\u6700\u591a\u5c31 \\(n\\sqrt n\\)\uff0c\u6240\u4ee5\u6240\u6709\u5339\u914d\u4e32\u5728\u6bcd\u4e32\u51fa\u73b0\u6b21\u6570\u4e4b\u548c\u4e3a \\(O(n\\sqrt n)\\) \u3002<\/p>\n <\/p>\n \u9996\u5148\u5efa AC\u81ea\u52a8\u673a\u662f\u80af\u5b9a\u7684\uff0c\u4f46\u662f\u6211\u4eec\u6709\u4e00\u4e2a\u5f88\u597d\u7684 \u52a8\u6001 \u7ebf\u6027\u8868\uff1a std::vector<><\/span> \uff01\uff01\uff01<\/p>\n \u6240\u4ee5\u5339\u914d\u5230\u4e00\u4e2a\u4e32\u5c31\u66b4\u529b\u63d2\u5230 std::vector<><\/span>\u00a0 \u91cc\uff0c\u6700\u540e\u5728\u91cc\u9762\u66b4\u529b\u627e\u3002<\/p>\n \u65f6\u7a7a\u590d\u6742\u5ea6 \\(O(n\\sqrt n)\\) \u3002<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":"zzx<\/code> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u96be\u5ea6\uff1a\\(6.0\\)<\/span><\/p>\n\n
\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\n
\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\n
\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\n
\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n
abbb\r\n7\r\n4 b\r\n1 ab\r\n3 bb\r\n1 abb\r\n2 bbb\r\n1 a\r\n2 abbb<\/pre>\n
\n
\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n
-1\r\n2\r\n-1\r\n3\r\n-1\r\n1\r\n-1<\/pre>\n
\n
\u5b50\u4efb\u52a1<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\n\n
\n \n\u6d4b\u8bd5\u70b9\u7f16\u53f7<\/th>\n \\(|s|\\)<\/th>\n \\(n\\)<\/th>\n \u7ea6\u5b9a<\/th>\n<\/tr>\n<\/thead>\n \n 1-3<\/td>\n \\(\\le 300\\)<\/td>\n \\(\\le 300\\)<\/td>\n \u65e0<\/td>\n<\/tr>\n \n 4-5<\/td>\n \\(\\le 5000\\)<\/td>\n \\(\\le 5000\\)<\/td>\n<\/tr>\n \n 6-7<\/td>\n \\(\\le 100000\\)<\/td>\n \\(\\le 100000\\)<\/td>\n \u5b57\u7b26\u4e32 \\(s\\) \u4ec5\u5305\u542b\u5b57\u7b26 a<\/td>\n<\/tr>\n \n 8-10<\/td>\n \\(\\le 50000\\)<\/td>\n \\(\\le 50000\\)<\/td>\n \u6bcf\u4e2a \\(m_i\\) \u5728 \\(s\\) \u4e2d\u51fa\u73b0\u6b21\u6570\u4e0d\u8d85\u8fc7 \\(50\\)<\/td>\n<\/tr>\n \n 11-12<\/td>\n \\(\\le 100000\\)<\/td>\n \\(\\le 100000\\)<\/td>\n<\/tr>\n \n 13-16<\/td>\n \\(\\le 50000\\)<\/td>\n \\(\\le 50000\\)<\/td>\n \u6240\u6709 \\(m_i\\) \u7684\u603b\u957f\u4e0d\u8d85\u8fc7 \\(50000\\)<\/td>\n<\/tr>\n \n 17-20<\/td>\n \\(\\le 100000\\)<\/td>\n \\(\\le 100000\\)<\/td>\n \u65e0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\nfail<\/code>\u6307\u9488\u5728\u6811\u4e0a\u542f\u53d1\u5f0f\u5408\u5e76\uff0c\u5bf9\u6811\u4e0a\u6240\u6709\u7684\u5339\u914d\u4e32\u7684\u7ec8\u6b62\u70b9\u8ba1\u7b97\u7b54\u6848\uff0c\u8ba1\u7b97\u7b54\u6848\u662f\u4e0e\u5339\u914d\u4e32\u5728\u6bcd\u4e32\u51fa\u73b0\u6b21\u6570\u7ebf\u6027\u76f8\u5173\u7684\u3002<\/p>\n#include <cstdio>\r\n#include <cstdlib>\r\n#include <cstring>\r\n#include <climits>\r\n#include <vector>\r\n\r\n#define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_))\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=getchar();\r\n\twhile(!(c>='0' && c<='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c>='0' && c<='9')\r\n\t\ta=a*10+c-'0',c=getchar();\r\n\treturn a;\r\n}\r\n\r\ntemplate<class T>\r\ninline void getstr(char s[],T&ls)\r\n{\r\n\tregister char c=0;\r\n\twhile(!(c>='a' && c<='z'))\r\n\t\tc=getchar();\r\n\tls=0;\r\n\twhile(c>='a' && c<='z')\r\n\t\ts[++ls]=c,c=getchar();\r\n\ts[ls+1]=0;\r\n\treturn;\r\n}\r\n\r\nint cnt,ch[105050][26],endidx[105050];\r\ninline void insertStr(char s[],register int ls,const int&idx)\r\n{\r\n\tregister int now=0;\r\n\tfor(register int i=1;i<=ls;i++)\r\n\t{\r\n\t\tregister short c=s[i]-'a';\r\n\t\tif(!ch[now][c])\r\n\t\t\tch[now][c]=++cnt;\r\n\t\tnow=ch[now][c];\r\n\t}\r\n\tendidx[now]=idx;\r\n}\r\n\r\nint fail[105050];\r\ninline void build()\r\n{\r\n\tstatic int lst[105050];\r\n\tregister int front=0,rear=0;\r\n\tfor(register int j=0;j<26;j++)\r\n\t\tif(ch[0][j])\r\n\t\t\tlst[rear++]=ch[0][j],fail[ch[0][j]]=0;\r\n\twhile(front<rear)\r\n\t{\r\n\t\tregister int now=lst[front++];\r\n\t\tfor(register int j=0;j<26;j++)\r\n\t\t\tif(ch[now][j])\r\n\t\t\t\tfail[ch[now][j]]=ch[fail[now]][j],lst[rear++]=ch[now][j];\r\n\t\t\telse\r\n\t\t\t\tch[now][j]=ch[fail[now]][j];\r\n\t}\r\n}\r\n\r\nchar s[105050],m[105050];\r\nunsigned lm[105050],k[105050];\r\nstd::vector<int>endpos[100001];\r\n\r\nint main()\r\n{\r\n\tint ls;getstr(s,ls);\r\n\tregister int N=getnum();\r\n\tfor(register int i=1;i<=N;i++)\r\n\t{\r\n\t\tk[i]=getnum();\r\n\t\tgetstr(m,lm[i]);\r\n\t\tinsertStr(m,lm[i],i);\r\n\t}\r\n\tbuild();\r\n\t\r\n\tregister int now=0;\r\n\tfor(register int i=1;i<=ls;i++)\r\n\t{\r\n\t\tregister short c=s[i]-'a';\r\n\t\tnow=ch[now][c];\r\n\t\tfor(register int j=now;j;j=fail[j])\r\n\t\t\tif(endidx[j])\r\n\t\t\t\tendpos[endidx[j]].push_back(i);\r\n\t}\r\n\t\r\n\tfor(register int i=1;i<=N;i++)\r\n\t{\r\n\t\tif(endpos[i].size() < k[i])\r\n\t\t{\r\n\t\t\tprintf(\"%d\\n\",-1);\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\t\r\n\t\tregister unsigned mlen=UINT_MAX;\r\n\t\tfor(register unsigned j=k[i];j<=endpos[i].size();j++)\r\n\t\t\tmlen=_min(mlen,endpos[i][j-1]-(endpos[i][j-1-k[i]+1]-lm[i]+1)+1);\r\n\t\tprintf(\"%u\\n\",mlen);\r\n\t}\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n