{"rsdb":{"rid":"397565","subhead":"","postdate":"0","aid":"273634","fid":"49","uid":"1","topic":"1","content":"
\n

\u524d\u8a00<\/h3> \n

\u6700\u8fd1\u624d\u53d1\u73b0\u81ea\u5df1\u5199\u4e86\u540e\u7f00\u6570\u7ec4\uff0c\u4f46\u5e76\u6ca1\u6709\u5176\u4ed6\u7684\u5b57\u7b26\u4e32\u7b97\u6cd5\uff0c\u4eca\u5929\u5148\u628a \\(KMP\\)<\/span> \u5b57\u7b26\u4e32\u5339\u914d\u5148\u8bb2\u4e00\u4e0b\u3002<\/p> \n

\u7b97\u6cd5\u6838\u5fc3<\/h3> \n

\u5bf9\u4e8e\u5b57\u7b26\u4e32\u5339\u914d\uff0c\u6700\u6734\u7d20\u7684\u65b9\u6cd5\u5c31\u662f\u4e00\u4e2a\u5b57\u7b26\u4e00\u4e2a\u5b57\u7b26\u5730\u5339\u914d\uff0c\u627e\u5230\u4e0d\u540c\u7684\u5c31\u76f4\u63a5\u6362\u4e00\u4e2a\u5730\u65b9\u5339\u914d\u3002<\/p> \n

\u6211\u4eec\u5148\u6765\u770b\u4e00\u7ec4\u6837\u4f8b\uff1a
\\(ababababe\\)<\/span><\/p> \n

\\(ababe\\)<\/span><\/p> \n

\u5bf9\u4e8e\u8fd9\u7ec4\u6837\u4f8b\uff0c\u66b4\u529b\u7684\u65b9\u6cd5\u5c31\u662f\u76f4\u63a5\u5339\u914d\uff0c\u4ece\u7b2c\u4e00\u4f4d\u5f00\u59cb\u5339\u914d\uff0c\u53d1\u73b0\u4ece\u7b2c\u4e94\u4e2a\u5730\u65b9\u5f00\u59cb\u4e0d\u4e00\u6837\u4e86\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u76f4\u63a5\u5f80\u540e\u79fb\uff1a
\\(ababababe\\)<\/span><\/p> \n

\\(\\,\\,\\, ababe\\)<\/span><\/p> \n

\u53d1\u73b0\u4ece\u7b2c\u4e94\u4f4d\u5f00\u59cb\u4e0d\u4e00\u6837\u4e86\uff0c\u7ee7\u7eed\u5f80\u540e\u9762\u79fb\uff1a<\/p> \n

\\(ababababe\\)<\/span><\/p> \n

\\(\\quad ababe\\)<\/span><\/p> \n

\\(\\dots\\dots\\)<\/span><\/p> \n

\u4ee5\u6b64\u7c7b\u63a8\uff0c\u6211\u4eec\u5728\u7b2c\u4e94\u4f4d\u53d1\u73b0\u6210\u529f\u5339\u914d\u4e86\u3002<\/p> \n

\u4e0d\u8fc7\u8fd9\u6837\u5339\u914d\u901f\u5ea6\u592a\u6162\u4e86\uff0c\u590d\u6742\u5ea6\u4e3a \\(O(nm)\\)<\/span>\uff0c\u7136\u540e\u6211\u4eec\u81ea\u5df1\u76f4\u63a5\u60f3\u80af\u5b9a\u4e0d\u4f1a\u4e00\u4e2a\u4e00\u4e2a\u7684\u6162\u6162\u60f3\uff0c\u6211\u4eec\u5728\u5339\u914d\u7b2c\u4e00\u4e2a\u5339\u914d\u5931\u8d25\u540e\u4f1a\u5c06\u6a21\u5f0f\u4e32\uff08\u4e5f\u5c31\u662f\u5c0f\u7684\u90a3\u4e00\u4e2a\uff09\u7b2c\u4e09\u7b2c\u56db\u4f4d\u76f4\u63a5\u79fb\u5230\u7b2c\u4e00\u7b2c\u4e8c\u4f4d\uff08\u56e0\u4e3a\u4ed6\u4eec\u76f8\u540c\uff09\u3002\u90a3\u4e48\u5c31\u53ef\u4ee5\u77e5\u9053 \\(KMP\\)<\/span> \u7684\u6838\u5fc3\u5176\u5b9e\u5c31\u5728\uff0c\u6bcf\u6b21\u5339\u914d\u5931\u8d25\u540e\uff0c\u5c06\u6a21\u5f0f\u4e32\u79fb\u5230\u76f8\u540c\u7684\u5730\u65b9\u3002<\/p> \n

\u7136\u540e\u5c31\u53ef\u4ee5\u60f3\u5230\u9884\u5904\u7406\u51fa\u4e00\u4e2a\u6570\u7ec4 \\(p\\)<\/span>\uff0c\\(p_j\\)<\/span> \u8868\u793a\u5728\u5339\u914d\u5230\u7b2c \\(j\\)<\/span> \u4e2a\u5b57\u6bcd\u800c \\(j+1\\)<\/span> \u4e2a\u5b57\u6bcd\u4e0d\u80fd\u5339\u914d\u662f\uff0c\u53ef\u4ee5\u79fb\u52a8\u5230\u524d\u9762\u548c\u5f53\u524d\u76f8\u540c\u7684\u5730\u65b9\uff0c\u4e5f\u5c31\u662f\u8981 \\(t_1t_2\\dots t_{p_j}=t_{j-p_j+1}t_{j-p_j+2}\\dots t_j\\)<\/span> \u7684\u6700\u5927\u503c\u3002<\/p> \n

\u7136\u540e\u4f7f\u5f97 \\(s_{i-j+1}s_{i-j+2}\\dots s_i=t_1t_2\\dots t_j\\)<\/span> \u7ee7\u7eed\u8fdb\u884c\u5339\u914d\u3002<\/p> \n

\u7136\u540e\u5c31\u5f88\u6e05\u6670\u4e86\u3002<\/p> \n

\\(p\\)<\/span> \u6570\u7ec4<\/h3> \n

\u81ea\u5df1\u5339\u914d\u81ea\u5df1\uff0c\u7136\u540e\u5c31\u53ef\u4ee5\u5728\u5339\u914d\u5931\u8d25\u7684\u65f6\u5019\u79fb\u52a8\u5230\u76f8\u540c\u7684\u5730\u65b9\u4ee5\u4f18\u5316\u3002<\/p> \n

\u4ee3\u7801\uff1a<\/h5> \n 
for(int i=1;i<m;++i){\n    while(j>0&&t[j+1]!=t[i+1])\n\t\tj=p[j];\n    if(t[i+1]==t[j+1])\n\t\t++j;\n\tp[i+1]=j;\n}\n<\/code><\/pre> \n 
Code<\/h3> \n 
#include<bits\/stdc++.h>\n#define int long long \nusing namespace std;\ninline int read(){\n\tint x=0,f=1;\n\tchar ch;\n\tch=getchar();\n\twhile(ch<'0'||ch>'9'){\n\t\tif(ch=='-') f=-f;\n\t\tch=getchar();\n\t}\n\twhile(ch>='0'&&ch<='9'){\n\t\tx=x*10+(ch-'0');\n\t\tch=getchar();\n\t}\n\treturn x*f;\n}\nchar s[10000000],t[10000000];\nint n,m,p[11000000];\nsigned main(){\n    scanf("%s%s",s+1,t+1);\n    p[1]=0;\n    n=strlen(s+1),m=strlen(t+1);\n    int j=0;\n    for(int i=1;i<m;++i){\n        while(j>0&&t[j+1]!=t[i+1])\n\t\t\tj=p[j];\n        if(t[i+1]==t[j+1])\n\t\t\t++j;\n\t\tp[i+1]=j;\n    }\n    j=0;\n    for(int i=0;i<n;++i){\n        while\n\t\t\tj=p[j];\n        if(t[j+1]==s[i+1])\n\t\t\t++j;\n        if(j==m){\n\t\t\tcout<<i-m+2<<endl;\n\t\t\tj=p[j];\n\t\t}\n    }\n    for(int i=1;i<=m;++i)printf("%d ",p[i]);\n    return 0;\n}\n<\/code><\/pre> \n 
\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a\uff1a\\(O(n+m)\\)<\/span>\uff08\u4e0d\u4f1a\u91cd\u590d\u5339\u914d\uff09\u3002<\/p> \n<\/div>","orderid":"0","title":"KMP \u5b57\u7b26\u4e32\u5339\u914d \u5b66\u4e60\u7b14\u8bb0","smalltitle":"","mid":"0","fname":"c++\u7f16\u7a0b\u57fa\u7840","special_id":"0","bak_id":"0","info":"0","hits":"501","pages":"1","comments":"0","posttime":"2023-09-23 15:44:34","list":"1695455074","username":"admin","author":"","copyfrom":"","copyfromurl":"","titlecolor":"","fonttype":"0","titleicon":"0","picurl":"https:\/\/www.cppentry.com\/upload_files\/","ispic":"0","yz":"1","yzer":"","yztime":"0","levels":"0","levelstime":"0","keywords":"KMP<\/A> \u7b26\u4e32\u5339<\/A> \u4e60\u7b14\u8bb0<\/A>","jumpurl":"","iframeurl":"","style":"","template":"a:3:{s:4:\"head\";s:0:\"\";s:4:\"foot\";s:0:\"\";s:8:\"bencandy\";s:0:\"\";}","target":"0","ip":"112.94.1.100","lastfid":"0","money":"0","buyuser":"","passwd":"","allowdown":"","allowview":"","editer":"","edittime":"0","begintime":"0","endtime":"0","description":"KMP \u5b57\u7b26\u4e32\u5339\u914d \u5b66\u4e60\u7b14\u8bb0","lastview":"1714284656","digg_num":"1221","digg_time":"1714133161","forbidcomment":"0","ifvote":"0","heart":"","htmlname":"","city_id":"0"},"page":"1"}