next[j]的含义是：在字串第j个字符匹配失败时，直接跳转到子串的下表为j的位置再与主串进行比较
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
void Find_next(string T,int next[])
{
int i=0,j=-1;
next[0]=-1;
while(i<T.length()-1)
{
if(j==-1||T[i]==T[j])
{
i++;
j++;
next[i]=j;
}
else
{
j=next[j];
}
}
}
int KMP(string S,string T,int next[])
{
int i=0;
int j=0;
while(i<S.length()&&j<T.length())
{
if(j==-1||S[i]==T[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j>=T.length())
return i-T.length();
return 0;
}
int main()
{
string S="ababbabsdfer";
string T="abbabsd";
int next[T.length()];
memset(next,0,sizeof(next));
Find_next(T,next);
for (int i = 0; i < T.length(); i++)
{
cout<<next[i]<<" ";
}
cout<<endl;
cout<<KMP(S,T,next)<<endl;
system("pause");
return 0;
}
