从KMP到BM，文本编辑器查找算法的进化之路，哪个算法才是文本搜索的终极利器？

引言 在学习KMP算法后，我不免想到KMP算法能在哪一个地方使用，KMP作为字符串匹配算法，我很容易想到了他的用武之地，那就是文本编辑器中的查找功能，然而，对于主流的文本编辑器而言，似乎没有多少使用KMP算法用于查找功能构建，而他们使用了一个更为高效的算法：BM算法。 一、KMP算法 1.1 暴力匹配 在理解KMP之前，先看最直观的暴力匹配法： 假设文本串 T = "ABABABC"，模式串 P = "ABABC"。 暴力匹配会在每个位置尝试对齐，一旦发现不匹配，就将模式串向右移动一位，重新开始比较。最坏情况下时间复杂度为 O(m×n)（m为文本长度，n为模式长度）。 1.2 KMP的核心思想 KMP算法的革命性在于：利用已匹配的信息，避免主串指针回退。 当匹配失败时，模式串不是简单地右移一位，而是根据预先计算的部分匹配表（Partial Match Table，也叫next数组），直接跳到下一个可能匹配的位置。 文本串：A B A B A B C 模式串：A B A B C ↑ 这里失配（A ≠ C） 暴力法：回退到文本串第2位，模式串回到开头 KMP： 根据next数组，模式串右移2位，保持文本串指针不动 1.3 next数组的构建 next数组记录的是模式串中最长相等前后缀的长度： 模式串P A B A B C 位置j 0 1 2 3 4 next[j] 0 0 1 2 0 暴力构建 我们的目标是求出每个子串的最长相等前后缀的长度，那么对于每个子串我们直接设立两个指针，一个从第二个字符开始，一个从倒数第二个字符开始，分别向后和向前扫，找到最长的相等前后缀。 优化一：利用相邻位置的单调性约束（O(n³) → O(n²)） 观察到：相邻的前缀函数值至多增加1，即 π[i+1] ≤ π[i] + 1 原理： 若 π[i+1] 要取最大值，必须满足 s[i+1] == s[π[i]]（新字符等于已匹配前缀的下一个字符） 此时 π[i+1] = π[i] + 1 若不满足，则 π[i+1] 必然小于 π[i] 优化效果： 内层循环的搜索范围从 [i, 0] 缩小到 [π[i-1]+1, 0] 字符串比较次数上限从O(n²)降至O(n)，总复杂度变为 O(n²) 优化二：利用已计算的π值进行链式跳转（O(n²) → O(n)） 观察到：失配时，次优解长度等于 π[π[i]-1] 原理： 当在位置 i 计算 π[i] 时，设 j = π[i-1]（即上一个最优长度）： 若匹配：s[i] == s[j]，则 π[i] = j + 1（直接继承+1） 若失配：s[i] != s[j]，需要找次长的相等前后缀长度 j' 关键性质：由于 s[0...j-1] == s[i-j...i-1]，那么次长解 j' 必须同时满足： 是 s[0...j-1] 的相等前后缀 因此 j' = π[j-1] 链式回退：若仍失配，继续取 j = π[j-1]，直到 j = 0 状态转移方程： j(n) = π[j(n-1) - 1], 其中 j(n-1) > 0 构建方法： int j = 0; for (int i=1;i<s.size();i++){ while (j>0 and s[i] != s[j])j = kmp[j-1]; if (s[i] == s[j]) j++; kmp[i] = j; } 1.4 KMP算法的实现 在获得了已计算好的前缀函数后，我们就可以避免在失配时从头比较，从而实现 \(O(n+m)\) 的线性匹配，这就是kmp算法所要做到的。 构造匹配字符串 将模式串、分隔符、文本串连接起来： \[\text{concat} = s + \# + t \] 其中 \(\#\) 是一个既不出现在 \(s\) 中也不出现在 \(t\) 中的分隔符。 为什么需要分隔符： 防止 \(s\) 的后缀与 \(t\) 的前缀错误匹配 确保前缀函数值在 \(s\) 和 \(t\) 的边界处不超过 \(|s|\) 前缀函数在匹配中的含义 对于构造好的字符串 \(\text{concat}\)，计算其前缀函数 \(\pi\)。