在文本串（text）中找模式串（pattern）时，如果用暴力查找基本是时间复杂度是（n*m），以i，j分别标志文本串、模式串当前匹配位置，如果text[i]和pattern[j]不等，pattern就要从头比较，实际上模式串的j前面的已经匹配好了，这样就比较浪费信息。
如果j的前几位和pattern开头的前几位相同，那这几位可以不用再比较，而kmp算法正是应用了这个特性，找到pattern当前j位置前几位和pattern开始几位相同的最大个数，减少了比较时间。
怎样描述一下这个最大个数，用一个next数组，next[j]表示pattern字符串第j位前前几位和pattern前几位相同的最大个数。
所以kmp算法的关键就是求一下模式串next数组。
next数组求解的思路是利用已知信息进行递归。
已知i前面的next值，现在看第i+1位，前面最大相等数值位next[i],现在后缀添加了一个字母pattern[i+1],如果前面i最大前缀前缀后一位字母pattern[next[i]]同它相等，显然next[i+1]=next[i]+1;但是不等怎么办！我们要寻找最大相等个数为k，则现在k已经小于next[i]了，我们有不妨找next[i]前面的最大相等位，另k=next[i],去找next[k]=next[i]+1,如此递归到找到或者k已经是起始位了为止。
根据这个思路：
代码如下：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=10001; int next[maxn];//next 数组标记位置 void getnext(char s[],int len) { int j=-1; next[0]=-1; for(int i=1;i<len;i++) { while(j!=-1&&s[i]!=s[j+1]) j=next[j]; if(s[i]==s[j+1]) j++; next[i]=j; } } int kmp(char text[],char pattern[]){ int ans=0,j=-1,n=strlen(text),m=strlen(pattern); getnext(pattern,m); for(int i=0;i<n;i++) { while(j!=-1&&text[i]!=pattern[j+1]) j=next[j]; if(text[i]==pattern[j+1]) j++; if(j==m-1){ ans++; j=next[j]; } } return ans; } int main(){ char a[]="ababab",b[]="ab"; int k=kmp(a,b); cout<<k; return 0; }
