看了好多博客，都觉得好难懂。怕忘了，自己总结一下。
要了解KMP，最重要的是懂得如何求next数组。
定义：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1到k个字符与开头的1到k个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。 即T[0]T[1]T[2]。。。T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1] 且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
解释：
（定义1）S[i]!=T[0],规定next[0]=-1,‘-1’只是一个标记，如果next[j]==-1，说明S[i]!=T[0]，下次比较应该比较（S[i+1],T[0]）
（定义2）S[i]!=T[j],但是T[j]==T[0]；i是S的pos，j是T的pos
例子一： T=abcda （1） T=abcda (2)
S=abcdea S=abcdea
(1)中(i=0,j=0)->(i=4，j=4)发现S[4]!=T[4]了，肉眼可以看出下一次比较应该是(i=5,j=0)即(S[i+1],T[0]),同定义1，因此我们将next[4]=-1
例子二：T=ababa （1） T=ababa (2) T=ababa (3)
S=ababea S=ababea S=ababea
(1)中(i=0,j=0)->(i=4，j=4)发现S[4]!=T[4]了，我们可以看到T[0]T[1]=T[2]T[3]=S[2]S[3]；T[4]=T[2]=T[0];我们有必要比较(S[2],T[0])吗（2），没有，因为我们知道S[2]S[3]S[4]!=T[0]T[1]T[2]
我们应该比较什么？(S[5],T[0])，因为我们知道S[2]S[3]S[4]不可能与T[0]T[1]T[2]匹配，S[3]S[4]不可能与T[0]T[1]匹配，S[4]不可能与T[0]匹配。
其中，如果S[3][4]=T[0]T[1],说明S[3][4]=T[0]T[1]=T[2]T[3],又T[3]=S[3],则T[0]T[1]T[2]T[3]T[4]S[3]S[4]都相同，这与S[4]T[4]不同相违背。
现在我们知道下一次应该比较(i=5,j=0)即(S[i+1],T[0]),同定义1，因此我们将next[4]=-1
(定义3)S[i]!=T[j],但是T[0]T[1 ]T[2]。。。T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1] 且T[j] != T[k];
例子：T=abcdabca （1） 这时候怎么比？ T= abcdabca （2）
S=abcdabcccccccc S=abcdabcccccccc
（1）中(i=0,j=0)->(i=7,j=7)发现S[7]!=T[7]了，但是T[0]T[1]T[2]=T[4]T[5]T[6]=S[4]S[5]S[6],这时我们应该比较（i=7,j=3）,因为J的前三位和T的前三位相同，所以next[7]=3
意味着，下次比较应该是(S[i],T[3])
(定义4)分析2,3，除2,3,外还有什么情况？
情况一：如果T为aa,那么可以套用定义2，但是为ab的话，S=aab,T=ab,比较发现(S[1]!=T[1]),下次比较应该是(S[1],T[0])，我们把这种情况记为’0‘，意味着i不变，j变为0
情况二：如果T为abc,S=aba或abc,由于不确定S[2]是否与T[0]相等，那么下次比较应该是(S[2],T[0]),发现i不变，j变为0，因此记为’0‘
next的意义：
设在S中查找模式串T，若S[M]!=T[N],那么T[N]的模式函数值next[N]，
1， next[N] = -1， 表示S[M]和T[0]间接比较过了，不相等，下一次比较(S[M+1],T[0])
2， next[N] = 0， 表示比较过程中产生了不相等，下一次比较S[M] 和S[0]
3， next[N] = K , 表示S[M]的前K个字符与T中开始的K个字符间接比较过，并且相等，下次比较(S[M],T[K])
其他值，不可能，上面的解释把各种情况总结过了，不信的话，自己找找特例。
如果T=a b a b c a a b c根据上面的判断，分析得
next=-1 0 -1 0 2 -1 1 0 2
我们用代码解决上面的思想
void getNext(char T[],int next[]){
int j=0,k=-1;next[0]=-1;//定义1 OK
while(T[j+1]!=' '){
if(k==-1||T[j]==T[k]){
j++;k++; //k的值就是开头的K个与J前面K个相等个数
if(T[j]!=T[k])next[j]=k;
else next[j]=next[k];
}else k=next[k];
}
for(int i=0;i<j;i++) cout<<next[i]<<endl;//检查是否正确
}
int main(){
char T[10]={'a','b','a','b','c','a','a','b','c'};
int next[10];
getNext(T,next);
return 0;
}
检查正确。
给出KMP的index函数
//返回子串T在主串S（从下标pos开始）中的位置，若不存在，则函数值为-1 int Index_KMP(char S[],char T[],int pos){ int i=pos,j=0; while(S[i]!='0'&&T[j]!='0'){ if(j==-1||S[i]==T[j]) i++,j++;//相等就比较下一个字符,j==-1,为了下次比较先将i++,j++ else{ j=next[j];}//下一次比较应在S[i]和T[next[j]]开始比较，其中，next[j]=-1的话，下次应该在S[i+1]和T[0]比较 } if(T[j]=='0') return i-j;//匹配成功，返回下标 else return -1;//匹配失败，返回-1 }