KMP算法 next数组 nextval数组
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
KMP算法过程主串：ababcabcacbab
模式串：abcac
我们可以发现与BF算法比较起来快速许多，BF算法在第二趟时i回溯到2位置，而KMP算法直接跳过前2个位置从第3个位置开始，而我们如何确定下一次比较时j的位置呢？我们这里用到了next数组。
| j | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 模式串 | a | b | c | a | c |
| next[j] | 0 | 1 | 1 | 1 | 2 |
next数组指示的是下一次匹配时j所在模式串位置，如上图第一趟匹配到j=3时失配，此时j=3，next[3]=1，所以我们让j=next[j]，再让主串i=3位置与模式串j=1位置进行比较，当j=0时我们让继续比较下一元素。
next数组实现代码void get_next(sstring T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
next[i+1]=j+1;
i++;j++;
}
else
j=next[j];
}
}
我们拿abcac模拟过程
1.第一位next=0；
2.第二位next=1；
3.第三位的next，第二位的模式串为b，next为1，我们拿第二位的b和第一位的a比较他们不相同，第三位的next=1；
4.第四位的next，第三位的模式串为c，next为1，我们拿第三位的c和第一位的a比较他们不相同，第四位的next=1；
5.第五位的next，第四位的模式串为a，next为1，我们拿第四位的a和第一位的a比较他们相同，第五位的的next=next[4]+1；
next值即为最长相同前后缀+1。
上面整个过程我们都在计算相同前后缀，这是个递推的过程，前后缀的概念可以这样理解，abcac中j=1时模式串为a，前面无元素，所以next=0，j=2是前缀后缀都为a但是所在位置相同所以next=1，j=3时前面的元素为ab，a和b不相同所以next=1，j=4时，前面元素为abc，依然不相同，next=1，j=5时，前面的元素为abca，前缀集合有｛a，ab，abc｝后缀集合有｛a，ca，bca｝只有a是相等的所以next=1+1=2。
递推过程中，我们先能得出前面元素的next值，这也就意味着我们知道了前面元素是否有相同前后缀，只要判断下一个元素是否与最长前缀的后一元素相等即可得到next值。
在我们看来next数组的应用已经使KMP算法很灵活了，但是有些情况下next数组却显得很笨重，如主串aaabbbg模式串aaaab。
我们可以得到next值依次为01234。
当i=4；j=4时主串为b，模式串为a，失配，next[4]=3，所以当j=3，a与主串中第4个位置的b依然不匹配，直到j=next[1]=0，i++；j++ i=5，j=1才匹配到，因为模式串中前4个a相同所以，我们只要让2，3，4号位置的next的值都变为0，匹配的过程就非常快。
代码如下
1.求next和nextval
void get_nextval1(sstring T,int next[],int nextval[]){
int i=1,j=0
next[1]=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;j++
next[i]=j;
if(T.ch[j]!=T.ch[next[j]])
nextval[j]=next[j];
else
nextval[j]=nextval[nextval[j]];
}
else
j=next[j];
}
}
2.只求nextval
void get_nextval2(sstring T,int nextval[]){
int i=1;j=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;j++;
if(T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
KMP算法的代码实现
#include
using namespace std;
typedef struct{
char ch[20];
int length;
}sstring;
void get_next(sstring T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
void get_nextval1(sstring T,int next[],int nextval[]){
int i=1,j=0;
next[1]=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;j++;
next[i]=j;
if(T.ch[j]!=T.ch[next[j]])
nextval[j]=next[j];
else
nextval[j]=nextval[nextval[j]];
}
else
j=next[j];
}
}
void get_nextval2(sstring T,int nextval[]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;j++;
if(T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
int KMP(sstring S,sstring T,int pos,int next[]){
int i=pos,j=1;
while(i<=S.length&&jT.length) return i-T.length;
else return 0;
}
void outstring(sstring S){
int i;
for(i=1;i<=S.length;i++)
cout<<S.ch[i];
cout<<endl;
}
int main(void){
sstring S,T;
int i,j,n,m;
int next[25]={-1},nextval[25]={-1};
cout<>n>>m;
getchar();
cout<<"请输入"<<n<<"个字符。"<<endl;
for(i=1;i<=n;i++){
S.ch[i]=getchar();
}
S.length=n;
getchar();
cout<<"请输入"<<m<<"个字符。"<<endl;
for(i=1;i<=m;i++){
T.ch[i]=getchar();
}
T.length=m;
getchar();
int pos;
cout<>pos;
get_next(T,next);
get_nextval2(T,nextval);
cout<<"next数组为：";
for(i=1;i<=m;i++)
cout<<next[i];
cout<<endl;
cout<<"nextval数组为：";
for(i=1;i<=m;i++)
cout<<nextval[i];
cout<<endl;
int status=KMP(S,T,pos,next);
if(status) cout<<"匹配成功，位置为："<<status<<endl;
else cout<<"匹配失败，主串中不含该模式串。"<<endl;
return 0;
}
实现效果
推荐两个B站视频能够帮助理解KMP算法
易懂版
详细版
作者：ToptimisticX
