从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数组），直接跳到下一个可能匹配的位置。

1. 文本串：A B A B A B C
2. 模式串：A B A B C
3.             ↑
4.           这里失配（A ≠ C）
5.          
6. 暴力法：回退到文本串第2位，模式串回到开头
7. KMP：   根据next数组，模式串右移2位，保持文本串指针不动

复制代码

1.3 next数组的构建

next数组记录的是模式串中最长相等前后缀的长度：
模式串PABABC位置j01234next[j]00120暴力构建

我们的目标是求出每个子串的最长相等前后缀的长度，那么对于每个子串我们直接设立两个指针，一个从第二个字符开始，一个从倒数第二个字符开始，分别向后和向前扫，找到最长的相等前后缀。
优化一：利用相邻位置的单调性约束（O(n³) → O(n²)）

观察到：相邻的前缀函数值至多增加1，即 π[i+1] ≤ π + 1
原理：

• 若 π[i+1] 要取最大值，必须满足 s[i+1] == s[π]（新字符等于已匹配前缀的下一个字符）
  
• 此时 π[i+1] = π + 1
  
• 若不满足，则 π[i+1] 必然小于 π
  

优化效果：

• 内层循环的搜索范围从 [i, 0] 缩小到 [π[i-1]+1, 0]
  
• 字符串比较次数上限从O(n²)降至O(n)，总复杂度变为 O(n²)
  

优化二：利用已计算的π值进行链式跳转（O(n²) → O(n)）

观察到：失配时，次优解长度等于 π[π-1]
原理：
当在位置 i 计算 π 时，设 j = π[i-1]（即上一个最优长度）：

• 若匹配：s == s[j]，则 π = j + 1（直接继承+1）
  
• 若失配：s != 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
  

状态转移方程：

1. j(n) = π[j(n-1) - 1], 其中 j(n-1) > 0

复制代码

构建方法：

1. int j = 0;
2. for (int i=1;i<s.size();i++){
3.     while (j>0 and s[i] != s[j])j = kmp[j-1];
4.     if (s[i] == s[j]) j++;
5.     kmp[i] = j;
6. }

复制代码

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\) 结尾的后缀中，与 \(s\) 的前缀相等的最长子串长度
  
• 若 \(\pi = n\)（模式串长度），意味着 \(s\) 完整出现在位置 \(i\)
  

下标换算：

• 位置 \(i\) 是在 \(\text{concat}\) 中的下标
  
• 在 \(t\) 中的实际起始位置为：\(i - (n-1) - (n+1) = i - 2n\)
  

即：出现位置 = \(i - 2 \times |s|\)

• 匹配过程可视化
  

1. concat = s + # + t
2.          ↓   ↓   ↓
3.         [0..n-1] [n] [n+1..n+m]
4.          
5. 当 π[i] = n 时（i 在 t 的部分）：
6.          s[0..n-1] 完全匹配到 t[i-n-(n+1)+1 .. i-(n+1)] = t[i-2n .. i-n-1]
7.          
8. 即 s 在 t 的位置 (i - 2n) 处出现

复制代码

• 算法实现
  

[code]vector find_occurrences(string text,string pattern){    string cur = pattern + '#' + text;    int sz1 = text.size(), sz2 = pattern.size();    vector pi = prefix_function(cur);    vector occurrences;    for (int i = sz2 + 1; i > P;    n = strlen(T);    m = strlen(P);    int cnt = bm_search();    cout