在文本T[1..n]中找到某个模式P[1..m]所有出现的位置被称作字符串匹配问题(m<=n)
P3375 【模板】KMP字符串匹配 这道题在洛谷上的评级居然是普及（？！）普及？？ QvQ 实现起来还是比较简单的，只不过有很多细节可以有很多种写法，看别人的代码容易凌乱。理解起来比较困难的部分是如何get_next
不建议初学者通过本文学习KMP算法，我的叙事能力极可能有问题 本文仅给出供参考的模板，如果你已经理解了思路，可以看一看
为了帮助理解程序，画了两个图表示next数组的预处理过程 另外 1. 该程序中的next[i]表示在p[i+1]匹配失败后下一次跳转到的位置 2. 该程序中的字符串都从0开始储存，到length-1 next[q-1]=k， 当我们匹配到p[q]==p[k]，则有next[q]=k+1
而当匹配到p[q]!=p[k]时…呢？我们把钴蓝色的长方形展开提取到next[k-1]，使k=next[k-1]。如果此时p[q]==p[k]，则有next[q]=next[k-1]+1；如果仍有p[q]!=p[k]，就再将青灰色的长方形展开（k=next[k-1]）…直到找到或k=0
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; int next[1005],n,m; char t[1000005],p[1005]; void get_next() { next[0]=0; int k=0; for(int q=1;q<m;q++) { while(k>0&&p[k]!=p[q])k=next[k-1]; if(p[k]==p[q])k++; next[q]=k; } } void kmp() { get_next(); int q=0; for(int i=0;i<n;i++) { while(q>0&&p[q]!=t[i])q=next[q-1]; if(p[q]==t[i])q++; if(q>=m) { printf("%d\n",i-m+2); q=next[q-1]; } } } int main() { scanf("%s%s",t,p); n=strlen(t); m=strlen(p); kmp(); for(int i=0;i<m;i++) printf("%d ",next[i]); return 0; }后续 呀，写完这篇忽然发现还是黄学长的写法比较好OrzOrzOrz我写的太凌乱了 链接：黄学长KMP 我要改写法。
