计数指针i和j分别指向主串S和模式串T中当前待比较的字符。由于每次比较失败后，同时回溯i和j，所以最坏时间复杂度为O(nm)。
int Index(string S, string T){ int i=1, j=1; while(i<=S.length && j<=T.length){ if(S[i]==T[j]){ //继续比较后续字符 i++; j++; } else{ i=i-j+2; j=1; //指针回溯 } } if(j>T.length) return i-T.length; else return 0; }主串S的计数指针i不回溯，模式串T的计数指针j=next[j]，即已经匹配过的相等字符不需要再次匹配。
相关概念 前缀：除最后一个字符外的所有头部子串； 后缀：除第一个字符外的所有尾部子串； 部分匹配值（PM）：字符串的前缀和后缀的最长相等前后缀长度 如‘aba’： ‘a’的前缀后缀都为空，最长相等前后缀长度为0 ‘ab’的前缀{a}，后缀{b}，最长相等前后缀长度为0 ‘aba’的前缀{a，ab}，后缀{a，ba}，最长相等前后缀长度为1 所以‘aba’的部分匹配值为001手工求next数组 求PM值——>PM表右移一位——>整体+1（根据题目选择） 比如求‘abcac’的next数组： 编号12345模式串abcacPM00010右移一位-10001next数组01112 代码求next数组 若T[i]=T[j]，next[i+1]=j+1；即两个橙蓝部分完全匹配 若不等，j=next[j]；即找前一个橙色的部分匹配值 void get_next(string T, int next[]){ int i=1, j=0; //i为移动标记，j为当前部分匹配值 next[1]=0; //将第1个字符的部分匹配值设为0 while(i<T.length){ if(j==0 || T[i]==T[j]){ i++;j++; next[i]=j; //下一个位置的部分匹配值 } else j=next[j]; //找前缀的部分匹配值 } } 求nextval数组 当字符串中有很多连续出现的字符时，比如模式串‘aaaab’和主串‘aaabaaaaab’，可以用nextval数组代替KMP算法中next数组，来优化算法，主要是将next[j]修改为next[next[j]]，有种递归的feel 可能选择题会用到，这里简单用递归的逻辑来求一下 编号123456789101112模式串ababaaababaanext011234223456nextval010104210104第1位：恒为0 第2位：next为1，与第1位比较，相同为next[1]，不同为next[2] 第3位：next为1，与第1位比较，相同为next[1]，不同为next[2] 第4位：next为2，与第2位比较，相同为next[2]，不同为next[4] 第5位：next为3，与第3位比较，相同为next[3]，不同为next[5] …
KMP代码实现 int Index_KMP(string S, string T, int next[]) { int i = 1, j = 1; while (i <= S.length && j <= T.length) { if (j == 0 || S[i] == T[j]) { i++; j++;//继续比较后面的字符 } else j = next[j];//模式串指针向右移动 } if (j > T.length) return i - T.length;//匹配成功 else return 0; }