KMP 算法 (Knuth&Morris&Pratt Algorithm)

· · 个人记录

KMP 算法 (Knuth&Morris&Pratt Algorithm)

找到所有 s_2 作为字符串 s_1 的字串的位置

朴素

枚举 i 作为 s_1 子串起点, j 作为正在比较的字符在 s_2 中的位置, 复杂度 O(mn)

Border

定义 border 为一个字符串的真子串, 既是母串的前缀, 又是母串的后缀

设 a_i 为字符串 s_2 的前 i 个字符组成的字符串的最长 border, 尝试 O(m) 求出 a_i

首先, 一定有 a_1 = 0, 假设对于 i', a_{i'} 已经求出, 则 a_{i} \leq a_{i - 1} + 1

首先考虑取等的情况, 当且仅当 {s_2}_{a_{i - 1} + 1} = {s_2}_i, 这时可以想象在 [1, i - 1] 的最长 border 之后接上字符 {s_2}_{a_{i - 1} + 1}, 构成了一个长度为 a_{i - 1} + 1 的 border

举例

AABAA                 // [1, 5]
AA___ ___AA           // a[5] = 2
AABAAB AAB___ ___AAB  // a[6] = 3

对于原不等式的证明, 使用反证法, 假设 [1, i] 存在长度大于 a_{i - 1} + 1 的 border, 即 a_i > a_{i - 1} + 1. 则去掉 {s_2}_i 后, [{s_2}_1, {s_2}_{a_{i} - 1}], 仍是 [1, i - 1] 的一个 border, 长度为 a_{i} - 1, 则 a_{i - 1} = a_i - 1 < a_i, 假设不成立, 原式得证.

对于 {s_2}_{a_{i - 1} + 1} \neq {s_2}_i 的情况, 根据 a_i \leq a_{i - 1} + 1, 不存在长度为 a_{i - 1} + 1 的 border, 所以只会存在长度小于 a_{i - 1} + 1 的 border. 由于 a_{i'} 的 border 已经求出, 而已知 [1, a_{i - 1}] 和 [i - a_{i - 1}, i - 1] 是匹配的, 所以可以知道 [1, i - 1] 的最长 border 的最长 border 也是相匹配的, 即 [1, a_{a_{i - 1}}] 和 [i - a_{a_{i - 1}}, i - 1] 是匹配的, 只要判断 {s_2}_{a_{a_{i - 1}} + 1} 和 {s_2}_i 是否相等即可

举例

ABAABA              // [1, 6]
ABA___ ___ABA       // a[6] = 3
ABAABAB             // [1, 7]
___A___ != ______B  // s[4] != s[7]
ABA A__ __A         // a_[a[6]] = a[3] = 1
_B_____ = ______B   // s[2] = s[7]
AB_____ _____AB     // a[7] = 2

对于这样求最长 border 的正确性证明, 和 a_i \leq a_{i - 1} + 1 的证明同理, 只要每次 border 末尾字符匹配失败时使枚举的长度 k = a[k] 即可.

接下来是复杂度分析, 由于每次递推时, a_i 最多会比 a_{i - 1} 增加 1, 所以对于最坏的情况, 即对于所有 i, 有 a_i = i - 1, 对于一个每次都匹配失败的 i, 需要循环 i 次, 然后使 a_i = 0, i 之后的子循环次数再次变成常数. 所以均摊复杂度 O(m)

匹配

枚举 i 作为 {s_2}_1 在 s_1 中的对应字符位置, 每次从匹配的字符往后扫, 直到字符不匹配或匹配成功. 这时, 已知 s_1[i, i + k - 1] 和 s_2[1, k] 匹配, 所以 s_1[i + k - a_k, i + k - 1] 和 s_2[1, a_k] 一定匹配, 此时对应 {s_2}_1 的字符是 {s_1}_{i + k - a_k}, 即 i = i + k - a_k. 而对于 i' \in (i, i + k - a_k), 一定不存在和 s_2 合法的匹配, 下面给出证明

仍是反证法, 对于 s_1[i, i + k - 1] 和 s_2[1, k] 已经匹配, 而 {s_1}_{i + k} \neq {s_2}_{k + 1} 的情况, 假设存在 i' \in (i, i + k - a_k) 使得 s_1[i', i' + m - 1] 和 s2 匹配, 则 s_1[i', i + k - 1] 和 s_2[1, i + k - i'] 匹配, 又因为 i' < i + k - a_k, 所以 i + k - i' > a_k. 这样一来, s_1[i', i + k - 1] 和 s_2[1, i + k - i'] 匹配和 {s_1}_{i + k} \neq {s_2}_{k + 1} 矛盾, 假设不成立, 原结论得证

所以每次匹配结束 (失败/成功) 后, 设已经匹配的长度为 k, 则直接使 i = i + k - a_k, k = a_k, 进行下一轮匹配, 保证不遗漏任何一个可行匹配

分析复杂度, 每次 s_1 有一个字符被成功匹配, {s_1}_i不会再和 s_2 中任何字符比较第二次. 所以分析 s_1 中字符匹配失败的概率. 发现失败次数和 k = a_k 递归层数有关, 根据上面求 a 数组时的分析, 发现失败次数均摊 O(1), 所以匹配的复杂度 O(n), 整个算法加上预处理的复杂度为 O(n + m)

代码

求 a 数组, 枚举 s_2 前缀长度 i

unsigned k(1);
for (register unsigned i(2); i <= lb; ++i)  { // Origin_Len
  while ((B[k] != B[i] && k > 1) || k > i) {
    k = a[k - 1] + 1; // 这里 k 相当于如果本次匹配成功得到的 border 长度 
  }
  if(B[k] == B[i]) { // 是匹配成功跳出而不是 a[k] = 0 溢出的 
    a[i] = k;
    ++k;
  }
}

匹配两个字符串, 代码中 k 的含义略有不同, 结合注释理解, 某些注释英语水平感人, 英文注释是出于打代码时害怕各种编辑器对中文的编码兼容性问题

k = 1;
for (register unsigned i(1); i + lb <= la + 1;) {  // Origin_Address
  while (A[i + k - 1] == B[k] && k <= lb) {
    ++k;  // 代码中 k 是待匹配的字符在 s_2 中的位置, 所以比实际匹配的长度多 1 
  }
  if(k == lb + 1) { // 匹配成功 
    printf("%u\n", i); 
  }
  if(a[k - 1] == 0) { // k = a[k] 的递归边界 
    ++i;
    k = 1;
    continue;
  }
  --k;            // k 是匹配失败的字符在 s_2 中的位置, 所以实际有 k - 1 长度的子串匹配成功 
  i += k - a[k];  // Substring of Len(k - 1) has already paired, so the next time, start with the border of the (k - 1) length substring
  k = a[k] + 1;   // 为什么我要写英文啊, 这是对 i 和 k 的同时移动, k = a[k] + 1 意思是在新起点已经匹配的 a[k] 长度的前缀之后的第一个字符开始比较 
}

模板 Luogu P3375