如果说next[j] = k,表明如果s[i] != p[j]的时候，j应该回溯到的pattern字符串的位置！
举例说明：
j 0 1 2 3 4 5 6 7 8 9 10
p[j] A B R A C A D A B R A
next[j] -1 0 0 0 1 0 1 0 1 2 3
默认情况下next[0] = -1，这是一个标示符，因为如果说next[j] = -1 即说明pattern的第一个字符就失配了，此时j不需要回溯，单纯的设置为-1
根据失配函数的定义，得到如下模式匹配规则：
1.如果出现了形如s[i-j]s[i-j+1]...s[i-1] = p[0]p[1]....p[j-1]且s[i] != p[j]的部分匹配，那么，若j != -1 则下一次模式匹配时，比较失配字符s[i]和p[next[j]]
2.若j = -1 ，则继续比较s[i+1]和p[0]，代码如下:
/*-----------------------------------算法4.6/4.7------------------------ -------------------------------------KMP------------------------------- -----------------------------------------------------------------------*/ #include <stdio.h> #include <string.h> #define maxn 10005 int next[maxn]; int KMP(char *s,char *p,int start_pos) { int i = start_pos,j = 0; while(i < strlen(s)){ if(s[i] == p[j] || j == -1){ ++i; ++j; } else j = next[j]; if(j == strlen(p)) return start_pos + (i - j); } return -1; } void GetNext(char *s) { int j = 0, k = -1; next[0] = -1; while(s[j] != \'\0\'){ if(s[j] == s[k] || k == -1){ j++; k++; next[j] = k; } else k = next[k]; } } int main() { char s[maxn] = {0}; char p[maxn] = {0}; scanf("%s",s); scanf("%s",p); int start_pos = 0; GetNext(p); int ans = KMP(s,p,start_pos); printf("%d\n",ans); return 0; }__________________________________________________________________________________________________________________________________________________________
会发现，next和KMP的写法很相近。
其实next就是把pat自己和自己进行模式匹配。
具体的证明————严蔚敏老师的《数据结构》有讲，而且很详细。