代码中l为前缀左指针r为后缀右指针公共前后缀是有“套娃性”的也可以叫局部对称性。这是l要回溯的原因。例如c处next[5] 3 。所以d处发现前后缀不匹配就要回溯到next[next[l]]处即next[3]1。此时最长公共前缀ab →a。如果仍然不匹配就会变成:a→(空)即next[1]0。这个过程就像 “剥洋葱”从最长的公共前后缀开始一层层往回找更短的前后缀直到找到能匹配的或回到 0空前缀这就是的 所谓的“套娃性”。#includestdio.h #includestring.h void get_next(char T[],int next[]) //下标从1开始 { // 初始状态 next[1] 0; int l 0; int r 1; while(T[r]!\0) { if(l0||T[l]T[r]) next[r]l; else lnext[l]; } } void get_next_0(char T[],int next[]) //下标从0开始 { // 初始状态 next[0] -1; int l -1; int r 0; while(T[r]!\0) { if(l-1||T[l]T[r]) next[r]l; else lnext[l]; } } void get_nextval_0(char T[], int nextval[]) { int len strlen(T); int next[80]; // 先生成普通next数组 get_next_0(T, next); // 初始化nextval[0] nextval[0] -1; // 遍历生成nextval下标1到len-1 for (int j 1; j len; j) { // 关键判断当前字符 和 回溯位置的字符是否相同 if (T[j] T[next[j]]) { nextval[j] nextval[next[j]]; // 直接继承更优位置的nextval } else { nextval[j] next[j]; // 不同则保留原next值 } } int kmp(char S[],char T[]) { int i0,j0;//遍历比较指针初始化,i属于主串 j属于模式串 int next[80]; get_next_0(T,next); while(S[i]!\0T[j]!\0) { if(S[i]T[j]) { i;j; } else{ //字符匹配失败只需让模式串回溯即可主串仍然前进直到主串末尾宣告失败 jnext[j]; //kmp无需全部回溯 if(j-1){i;j;}//特殊情况j回溯到-1彻底无匹配 } } if(T[j]\0) return(i-strlen(T)1); //1表示位置从1开始计数 else return 0;//失败返回0 } int main() { char s[30]abzababcdcsdabc; char t[20]ababcd; int res kmp(s,t); printf(%d,res); }例如0123456ababcd011231代码模拟-ababcd初始轮 l0,r1,next[1]0lr0第一轮 符合l0整体后移next[2]1;lr01第二轮 不符合走elsel回溯l next[l] 0l r01第三轮 符合l0整体后移next[3]1l r011第四轮符合T[1] T[3] 即aa整体连续后移next[4]2l r0112第五轮符合T[2] T[4] 即bb整体连续后移next[5]3l r01123第六轮不符合T[3]a ! T[5]c ,走elsel回溯l next[l] 1处l r01123第七轮不符合T[1]a ! T[5]c ,走elsel回溯l next[l] 0处l r01123第八轮符合l0整体后移next[6]1得到最终next数组ababcd011231