1.为什么需要 KMP假设我们有一个文本串 T长度 n和一个模式串 P长度 m想在 T 中找到 P 的所有出现。最简单的办法就是暴力匹配int brute_force(const char *s, const char *t){ //扫描文本串的每一位 for(int i 0; s[i]; i){ bool flag true; //用当前的第i位和模式串向后比较 for(int j 0; t[j]; j){ if(s[i j] t[j]) continue; flag false; break; } if(flag) return i; } return -1; }最坏情况下时间复杂度是 O(n×m)。暴力匹配慢在哪里回溯。当某一次匹配失配时文本指针会回退到上次起点的下一个位置模式指针直接归零导致大量重复比较。而 KMP 的核心思想就是当字符串匹配失败时主串的指针不回溯而是利用已匹配部分的信息将模式串“滑动”到一个最远的可能匹配位置从而避免不必要的比较。2.前缀函数与 next 数组2.1 前缀和后缀1真前缀从第一个字符开始不包含最后一个字符的所有连续子串。例如 abab 的真前缀有a, ab, aba。2真后缀从最后一个字符结束不包含第一个字符的所有连续子串。例如 abab 的真后缀有b, ab, bab。3最长相等真前缀和真后缀的长度对于模式串的每个位置 i定义 next[i] k 表示在子串 P[0..i] 中最长的相等真前缀与真后缀的长度为 k。且规定 k i1即不能是整个子串本身。举个例子模式串 ABABCi P[0..i] 最长相等真前缀/真后缀 k next[i] 0 A 无真前缀/真后缀皆为空 0 1 AB 无 0 2 ABA A 长度 1 1 3 ABAB AB 长度 2 2 4 ABABC 无 0所以 next 数组为 [0, 0, 1, 2, 0]。2.2 next数组next[i] 0 意义表示子串 P[0..i] 中没有相等的真前缀与真后缀。这意味着如果匹配到第 i 个字符时失配需要将模式指针回退到 0next[i] k (k0) 意义意味着 P[0..k-1] P[i-k1..i]。即模式串的前 k 个字符恰好等于子串末尾的 k 个字符。如果在第 i1 个字符即下标 i1处发生失配我们就可以将模式串向右滑动 i1 - k 位让模式的前 k 个字符直接对准文本中刚刚匹配成功的末尾 k 个字符从而避免重复比较。3.普通版本 KMP 的匹配在匹配时我们使用两个指针i文本串 T 的当前字符下标从不回退只向前移动j模式串 P 的当前要比较的下标根据 next 数组回退当 T[i] ! P[j]失配时的处理如果 j 0模式串第一个字符就不匹配则直接让 ij 保持为 0。如果 j 0说明前面已有部分字符匹配成功此时利用 next 数组获得当前已匹配部分的最长公共前后缀长度将 j 跳转到 next[j-1]从而复用已有匹配结果。void get_next(const char *pattern, int *next) { int m strlen(pattern); next[0] 0; // 第一位固定 0 int j 0; // 前缀指针 for (int i 1; i m; i) { // 不匹配j 回退 while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; } // 匹配j 后移 if (pattern[i] pattern[j]) { j; } next[i] j; } } int kmp_search(const char* text, const char* pattern, int next[]) { int n strlen(text); int m strlen(pattern); int i 0, j 0; while (i n) { if (text[i] pattern[j]) { i; j; } if (j m) { return i - j; // 匹配成功 } else if (i n text[i] ! pattern[j]) { // 失配时的处理 if (j ! 0) { j next[j - 1]; } else { i; // j0没法回退文本往前走 } } } return -1; }4.普通版本 next 函数的不足模式串AAAAB普通 next 数组index: 0 1 2 3 4 char : A A A A B next : 0 1 2 3 0假设在 j 3第四个 A失配j next[j-1] next[2] 2 j next[1] 1 j next[0] 0问题回退的每一步字符都是 A 但文本字符不是 A 所以这些回退 全部无效、全部浪费时间。优化思路如果 P[j] 模式串 P[ next[j-1] ]那么当在 j 处失配时回退到 next[j-1] 后依然会立即失配字符相同应该继续回退到更前的位置。 即直接令 nextval[j] nextval[ next[j-1] ]跳过冗余步骤。5.优化版本 KMP 的匹配为了避免无效回退我们对 next 数组进行改进得到 nextval 数组。其核心思想是如果回退后的字符与当前失配字符相同则继续回退直到不同或回到起点。5.1 nextval数组的计算1next[0] -1任何串的第一个字符的模式值规定为 -1。2next[j] -1若当前位置 j 不存在长度大于 0 的相等真前后缀并且 P[j] P[0]则回退到首字符后仍会立即失配。3next[j] k如果存在某个 k (1 ≤ k j)使得T[0..k-1] T[j-k..j-1]并且 P[j] ≠ P[k]则 next[j] kk 取满足条件的最大值。4next[j] next[k]若存在最大的 k1 ≤ k j满足 P[0..k-1] P[j-k..j-1]但 P[j] P[k] 说明回退到 k 后仍会比较相同字符必然再次失配。从本质上来讲-1 首字符 或 当前失配字符和首字符重复T[j] T[0]从头比也白比0 啥都不满足、无匹配、有匹配但字符撞车、首尾不等也没回退位置从T[0]开始重新比较。k 有最长相等前后缀 且 当前字符 ≠ k 位置字符有最长前后缀且字符不撞跳到 k 接着比。void getNext(const char* str, int* next) { int len strlen(str); int j 0; // 后缀指针 int k -1; // 前缀指针 next[0] -1; // 规则1首字符固定 -1 while (j len - 1) { if (k -1 || pattern[j] pattern[k]) { j; k; next[j] k; } else { k next[k]; } } }例模式串 P ABABC初始化j0k−1next[0]−11求 next [1]j0k−1满足 k−1j1k0next[1]02求 next [2]比较 P[j1]B 与 P[k0]A不相等knext[k0]−1现在 k−1j2k0next[2]03求 next [3]比较 P[j2]A 与 P[k0]A相等j3k1next[3]14求 next [4]比较 P[j3]B 与 P[k1]B相等j4k2next[4]2最终 next 数组[-1, 0, 0, 1, 2]5.2 KMP 匹配主算法int KMP(const char* text, const char* pattern) { int n strlen(text); int m strlen(pattern); int* next new int[m]; getNext(pattern, next); int i 0; int j 0; while (i n j m) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } } delete[] next; if (j m) return i - j; return -1; }