从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\)。 观察到：考虑 \(\pi\) 数组在 \(t\) 对应部分（即下标 \([n+1, n+m]\)）的值： \(\pi[i]\) 表示：以位置 \(i\) 结尾的后缀中，与 \(s\) 的前缀相等的最长子串长度 若 \(\pi[i] = n\)（模式串长度），意味着 \(s\) 完整出现在位置 \(i\) 下标换算： 位置 \(i\) 是在 \(\text{concat}\) 中的下标 在 \(t\) 中的实际起始位置为：\(i - (n-1) - (n+1) = i - 2n\) 即：出现位置 = \(i - 2 \times |s|\) 匹配过程可视化 concat = s + # + t ↓ ↓ ↓ [0..n-1] [n] [n+1..n+m] 当 π[i] = n 时（i 在 t 的部分）： s[0..n-1] 完全匹配到 t[i-n-(n+1)+1 .. i-(n+1)] = t[i-2n .. i-n-1] 即 s 在 t 的位置 (i - 2n) 处出现 算法实现 vector<int> find_occurrences(string text,string pattern){ string cur = pattern + '#' + text; int sz1 = text.size(), sz2 = pattern.size(); vector<int> pi = prefix_function(cur); vector<int> occurrences; for (int i = sz2 + 1; i <= sz1 + sz2; i++) { if (pi[i] == sz2) { occurrences.push_back(i - 2 * sz2); } } return occurrences; } 在线优化版本 如果已知前缀函数值不会超过特定值（即 \(|s|\)），可以不存储整个字符串，只保留 \(s+\#\) 部分，逐个读入 \(t\) 的字符并实时计算。 int j = 0; for (int i=0;i<t.size();i++){ while (j>0 and t[i] != s[j]) j = kmp[j-1]; if (t[i] == s[j]) j++; if (j == s.size()){ cout<<i-j+1<<endl; } } 1.5 KMP的时间复杂度 预处理：构建next数组需要 O(n) 匹配过程：文本串指针从不回退，O(m) 总复杂度：O(m + n) 二、KMP的局限性：为什么还不够快？ 尽管KMP在理论上已经很优雅，但在实际工程应用（如文本编辑器）中，它并非最优选择。原因如下： 2.1 比较顺序的"保守" KMP采用从左到右的顺序比较字符。这意味着： 文本串：... X X X X X X X X X X X X X A ... 模式串：A A A A A A A A A A A A A B ↑ 失配点 在这个例子中，KMP需要比较13个'A'后才发现最后一个字符是'B'不匹配。虽然利用next数组可以避免文本串回退，但已经做的比较都是"无用功"——我们本可以更早发现不匹配。 2.2 对字符集规模的忽视 KMP只关注模式串自身的结构（通过next数组），却忽略了文本串的实际内容。它没有利用"字符不匹配"这一信息来做出更大的跳跃。 2.3 自然语言限制 KMP算法主要对存在多个重复不完整片段的字符串进行优化，然而，自然语言中这种情况的出现过于苛刻，因此，其复杂度其实相较暴力并没有什么提升，因此并不是作为文本查找算法的最优解。 三、BM算法 针对KMP的局限性，1977年Robert S. Boyer和J. Strother Moore提出了Boyer-Moore算法。它彻底改变了字符串匹配的思路，成为现代文本编辑器的首选算法。 3.1 核心思想：从右向左比较 BM最大的创新是从模式串的末尾开始比较，这种比较方式提供了许多不错的特性，利用这些特性，我们可以最大化跳跃不可能匹配的情况： 文本串:H E R E I S A S I M P L E E X A M P L E 模式串:E X A M P L E ↑ 先比较这里（从右向左） 这种"反向比较"的策略带来了两个巨大的优势： 早发现早跳跃：如果不匹配发生在模式串尾部，我们可以立即获得大量信息 利用文本内容：根据文本中实际出现的字符，决定跳跃距离 3.2 坏字符规则（Bad Character Rule） 当文本串中的字符 c 与模式串对应位置不匹配时： 注意这里的字符c指的不是特定字符，而是一个变量 情况1：如果 c 根本不在模式串中，模式串可以直接跳过这个字符： 文本串：... A B C D E F G ... 模式串： T H I N G ↑ 比较E与G，不匹配，且E不在"THING"中 结果： 模式串直接右移5位（模式串长度） 情况2：如果 c 在模式串中存在，将模式串中最右侧的 c 对齐到当前位置： 文本串：... A B C D E F G ... 模式串： T H E N G ↑ 比较E与G，不匹配，但E在"THENG"中存在（位置1） 结果： 右移3位，将模式串中的E对齐到文本串的E 3.3 好后缀规则（Good Suffix Rule） 这是BM的第二个启发式规则，与KMP的思想类似，但应用在模式串的后缀上： 当已经匹配了模式串的一个后缀，但在前一个字符失配时： 文本串：... A B C D E F G H I J ... 模式串： F G H I J K G H I J ↑ 失配（F ≠ K） 但已匹配"GHIJ"（好后缀） 规则：在模式串中寻找另一个出现该后缀的位置，且前一个字符不同，然后对齐。 如果找不到完整后缀，则寻找最长匹配的前缀。 可以看到，BM算法经常能实现多字符跳跃，而不是KMP的逐个移动。 3.4 BM的简化代码 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; const int MAXM = 100005; const int SIGMA = 256; char T[MAXN], P[MAXM]; int n, m, delta1[SIGMA], delta2[MAXM], ans[MAXN]; // Z函数 O(n) vector<int> z_function(const string &s) { int n = s.size(); vector<int> z(n); for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } inline void build_delta1() { for (int i = 0; i < SIGMA; i++) delta1[i] = m; for (int i = 0; i < m - 1; i++) delta1[(unsigned char)P[i]] = m - 1 - i; } // O(m) 好后缀表，使用Z函数计算suff数组 inline void build_delta2() { // 计算suff[i]: 以i结尾的后缀与模式串前缀的最长匹配 vector<int> suff(m); string revP(P, m); reverse(revP.begin(), revP.end()); vector<int> z = z_function(revP); for (int i = 0; i < m; i++) suff[i] = (i == m - 1) ? m : z[m - 2 - i]; // 注意下标映射 // 初始化 for (int i = 0; i < m; i++) delta2[i] = m; // 情况2: 好后缀的后缀是模式串前缀 // 即 P[0..k-1] = P[m-k..m-1]，找最小的k使得失配位置j满足条件 int j = 0; for (int i = m - 1; i >= 0; i--) { if (suff[i] == i + 1) { // P[0..i]是P的后缀 while (j < m - 1 - i) { delta2[j] = m - 1 - i; j++; } } } // 情况1: 好后缀在模式串中还有其他出现（利用suff） for (int i = 0; i < m - 1; i++) { int pos = m - 1 - suff[i]; delta2[pos] = min(delta2[pos], m - 1 - i); } } inline int bm_search() { build_delta1(); build_delta2(); int cnt = 0, i = 0; while (i <= n - m) { int j = m - 1; while (j >= 0 && P[j] == T[i + j]) j--; if (j < 0) { ans[cnt++] = i; i += m > 1 ? delta2[0] : 1; } else { int bc = delta1[(unsigned char)T[i + j]] - (m - 1 - j); if (bc < 1) bc = 1; int gs = (j < m - 1) ? delta2[j] : m; i += max(bc, gs); } } return cnt; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> T >> P; n = strlen(T); m = strlen(P); int cnt = bm_search(); cout << cnt << "\n"; for (int i = 0; i < cnt; i++) cout << ans[i] << " \n"[i == cnt - 1]; return 0; } 四、算法对比 特性 KMP BM 比较方向 从左到右 从右到左 最佳情况 O(m) O(n/m)（亚线性！） 最坏情况 O(m+n) O(m×n)（但极少发生） 实际平均 O(m+n) O(n/m) ~ O(n) 预处理 O(n) O(n + σ)（σ为字符集大小） 适用场景 二进制数据、小字符集 自然语言、大字符集 五、总结 从KMP到BM，字符串匹配算法的发展体现了算法设计的核心哲学：利用一切可利用的信息。 KMP利用的是模式串自身的结构信息（next数组），消除了主串指针的回退，是理论上的突破。 BM则更进一步，同时利用模式串结构和文本串内容（坏字符），通过反向比较策略实现了工程上的飞跃，与此同时BM还有许多更好的优化方式，能够最大化的跳过不可能的部分，因此在工程上经常被采用。 对于现代文本编辑器而言，BM及其变种（如Horspool简化版、Sunday算法）凭借其实际的高效性，成为了查找替换功能使用的算法。