一、BF算法的问题回顾BF算法当匹配失败时text主串: a b c a b d 模式: a b d ↑ ↑ ✗ (c ! d)此时i回溯到2j重置为1重新开始比较。问题是我们已经知道S[2]b而T[1]a肯定不匹配。BF算法没有利用这个信息做了很多无用的比较。KMP的核心思想当匹配失败时主串指针i不回溯只移动模式串指针j利用已匹配部分的前缀和后缀信息跳过不必要的比较。二、前缀、后缀和部分匹配值2.1 定义前缀除最后一个字符外字符串的所有头部子串后缀除第一个字符外字符串的所有尾部子串部分匹配值前缀和后缀的最长相等长度例如ababa长度前缀后缀是否相等1aa✓2abba✗3abaaba✓4ababbaba✗最长相等长度为3所以部分匹配值为3。2.2 计算模式串的部分匹配值以T abab为例子串前缀后缀最长相等长度a空空0ab{a}{b}0aba{a,ab}{a,ba}1 (a)abab{a,ab,aba}{b,ab,bab}2 (ab)得到部分匹配值数组[0, 0, 1, 2]三、next数组的推导3.1 next数组的含义next[j]表示当模式串的第j个字符与主串不匹配时模式串指针j应该跳到的位置即下一次从哪个位置开始比较。重要约定为了方便我们通常让数组下标从1开始next[1] 0表示特殊情况。3.2 递推公式textnext[1] 0 next[2] 1 当 j 2 时 令 k next[j-1] 如果 T[j-1] T[k]则 next[j] k 1 否则递归地让 k next[k]继续比较直到 k0这个递推关系比较抽象我们通过具体例子来理解。3.3 手算next数组例1T ababtextj1: next[1] 0 j2: next[2] 1 j3: 看前一个字符 T[2]b 取 k next[2]1 比较 T[2] 和 T[1]: b ! a 让 k next[1]0k0 停止 next[3] k1 1 j4: 看前一个字符 T[3]a 取 k next[3]1 比较 T[3] 和 T[1]: a a匹配 next[4] k1 2结果next [0, 1, 1, 2]例2T abcabctextj1: next[1]0 j2: next[2]1 j3: T[2]b, k1, T[1]a, b!a, k0 → next[3]1 j4: T[3]c, k1, T[1]a, c!a, k0 → next[4]1 j5: T[4]a, k1, T[1]a, aa → next[5]2 j6: T[5]b, k2, T[2]b, bb → next[6]3结果next [0, 1, 1, 1, 2, 3]3.4 代码实现next数组cvoid getNext(const char *T, int *next, int len) { int i 1, j 0; // i是模式串当前下标j是已匹配的前缀长度 next[1] 0; while (i len) { if (j 0 || T[i-1] T[j-1]) { // 注意字符串下标从0开始 i; j; next[i] j; } else { j next[j]; } } }四、KMP匹配算法4.1 算法流程有了next数组KMP匹配就很简洁了texti 1, j 1 while (i S.len j T.len) { if (j 0 || S[i] T[j]) { i; j; } else { j next[j]; // i不回溯j跳转 } } if (j T.len) 返回 i - T.len else 返回 04.2 动画演示以S ababcabc,T abcabc为例next [0,1,1,1,2,3]text第1轮i1,j1 S: a b a b c a b c T: a b c a b c ↑ ↑ ✗ (aa, bb, a!c) 此时 j3根据next[3]1j跳到1 i保持3 第2轮i3,j1 S: a b a b c a b c T: a b c a b c ↑ ✗ (a!a? 等等S[3]a, T[1]a相等!) 等等仔细看S[3]a, T[1]a匹配实际上KMP的关键是当不匹配时j跳转到next[j]继续比较。4.3 完整代码c#include stdio.h #include string.h #include stdlib.h #define MAXLEN 100 // 获取next数组下标从1开始 void getNext(const char *T, int *next, int len) { int i 1, j 0; next[1] 0; while (i len) { if (j 0 || T[i-1] T[j-1]) { i; j; next[i] j; } else { j next[j]; } } } // KMP算法 int kmp(const char *S, const char *T) { int lenS strlen(S); int lenT strlen(T); if (lenT 0) return 1; if (lenS lenT) return 0; int *next (int*)malloc((lenT 1) * sizeof(int)); getNext(T, next, lenT); int i 1, j 1; // 从1开始 while (i lenS j lenT) { if (j 0 || S[i-1] T[j-1]) { i; j; } else { j next[j]; } } free(next); if (j lenT) { return i - lenT; // 返回位置从1开始 } return 0; } // 打印next数组 void printNext(const char *T) { int len strlen(T); int *next (int*)malloc((len 1) * sizeof(int)); getNext(T, next, len); printf(T \%s\\n, T); printf(j: ); for (int i 1; i len; i) { printf(%2d , i); } printf(\nnext: ); for (int i 1; i len; i) { printf(%2d , next[i]); } printf(\n\n); free(next); } int main() { // 测试next数组 printNext(abab); printNext(abcabc); printNext(aaaaa); // 测试匹配 printf(--- 匹配测试 ---\n); printf(abcabd 找 abd: %d\n, kmp(abcabd, abd)); printf(hello world 找 world: %d\n, kmp(hello world, world)); printf(aaaaa 找 aaa: %d\n, kmp(aaaaa, aaa)); printf(abc 找 def: %d\n, kmp(abc, def)); return 0; }运行结果textT abab j: 1 2 3 4 next: 0 1 1 2 T abcabc j: 1 2 3 4 5 6 next: 0 1 1 1 2 3 T aaaaa j: 1 2 3 4 5 next: 0 1 2 3 4 --- 匹配测试 --- abcabd 找 abd: 4 hello world 找 world: 7 aaaaa 找 aaa: 1 abc 找 def: 0五、nextval数组优化5.1 next数组的问题当T[j] T[next[j]]时匹配失败后跳转到next[j]但该位置的字符和当前字符相同仍然会失败造成额外比较。例如T aaaabtextj4, T[4]a, next[4]3, T[3]a相同 匹配失败后j4 → j3 → j2 → j1连续跳转多次5.2 nextval优化递归地优化如果T[j] T[next[j]]则nextval[j] nextval[next[j]]。计算nextvaltextnextval[1] 0 for j 2 to len: if T[j] T[next[j]]: nextval[j] nextval[next[j]] else: nextval[j] next[j]5.3 代码实现cvoid getNextval(const char *T, int *nextval, int len) { int i 1, j 0; nextval[1] 0; while (i len) { if (j 0 || T[i-1] T[j-1]) { i; j; if (T[i-1] ! T[j-1]) { nextval[i] j; } else { nextval[i] nextval[j]; } } else { j nextval[j]; } } }六、复杂度分析算法时间复杂度空间复杂度BFO(n×m)O(1)KMPO(nm)O(m)next数组KMP的优越性在大规模文本匹配中非常明显。例如主串长度 n1,000,000模式串长度 m1,000BF最坏需要 10^9 次比较KMP只需要约 1,001,000 次比较七、KMP与BF的对比对比项BF算法KMP算法主串指针会回溯不回溯模式串指针重置为1跳转到next[j]预处理无计算next数组时间复杂度O(n×m)O(nm)空间复杂度O(1)O(m)适用场景小规模、简单匹配大规模、多次匹配八、小结这一篇我们学习了KMP算法要点说明核心思想主串指针不回溯利用部分匹配信息移动模式串next数组表示匹配失败时j应该跳到的位置next推导递推公式基于前缀和后缀的相等关系nextval优化避免连续跳转到相同字符时间复杂度O(nm)比BF的O(n×m)高效很多KMP的精髓当匹配失败时我们已经知道前面哪些字符是匹配的利用这个信息跳过不必要的比较。下一篇我们讲数组的压缩存储。九、思考题模式串abcaabca的next数组是多少手动推导一下。KMP算法中主串指针为什么不回溯这样会不会漏掉可能的匹配如果模式串是abc它的next数组是多少匹配abcabc时KMP和BF的比较次数分别是多少什么时候用KMP比BF好什么时候BF其实就够了