跳转到内容
← 返回算法
经典算法计算机科学 · 算法 · 字符串处理约 16 分钟阅读

字符串匹配

String Matching

每次你按下 Ctrl+F 搜索一个词，每次你的 IDE 给你标出一个错误，每次 grep 在日志文件里找到一行记录——背后都有一个字符串匹配算法在工作。 字符串匹配听起来简单：给定文本 T（长度 n）和模式 P（长度 m），找出 P 在 T 中所有出现的位置。但"如何高效地做"这件事，包含了计算机科学中一些最精妙的思想…

字符串匹配KMP算法Boyer-Moore模式匹配文本搜索

每次你按下 Ctrl+F 搜索一个词，每次你的 IDE 给你标出一个错误，每次 grep 在日志文件里找到一行记录——背后都有一个字符串匹配算法在工作。

字符串匹配听起来简单：给定文本 T（长度 n）和模式 P（长度 m），找出 P 在 T 中所有出现的位置。但"如何高效地做"这件事，包含了计算机科学中一些最精妙的思想。

破除误解：暴力匹配不够用

最直觉的方法是：对文本 T 中的每个位置 i，检查从 i 开始的 m 个字符是否与模式 P 完全匹配。

python
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:  # 比较 m 个字符
            print(f"找到位置 {i}")
```

这个方法的时间复杂度是 $O(nm)$——在最坏情况下，每个位置都要比较 m 次。

对于短文本这没问题，但当 T 是一个 10 GB 的日志文件，P 是一个 100 字符的错误消息，$O(nm)$ 就有 101210^{12} 次操作，需要等几分钟——完全不可接受。

更糟的是，暴力匹配"浪费"了比较过程中已经获得的信息：当匹配在位置 i 失败时，我们已经知道了 T[i..i+k] = P[0..k]（前 k 个字符匹配），但暴力算法把这个信息完全丢弃，从 i+1 重新开始。

KMP 算法的突破，正是来自对这个"丢弃信息"问题的彻底解决。

KMP 算法：利用失败中的信息

1977 年，高德纳（Donald Knuth）、詹姆斯·莫里斯（James H. Morris）和沃恩·普拉特（Vaughan R. Pratt）联合发表了 KMP 算法（也是在 Morris-Pratt 1970 年工作的基础上改进的）。

KMP 的核心思想：预处理模式 P，构建一张"失败函数表"，告诉我们在任何位置匹配失败时，应该从模式的哪个位置重新开始比较——而不是回到 P[0]。

失败函数（Failure Function）

失败函数 fail[k] 的定义：模式 P[0..k] 的最长真前缀，使得这个前缀也是 P[0..k] 的一个后缀。

举例，模式 P = "ABABC"：

kP[0..k]最长真前后缀相同的前缀fail[k]
0A无0
1AB无0
2ABAA（前缀A = 后缀A）1
3ABABAB（前缀AB = 后缀AB）2
4ABABC无0
python
def build_fail(pattern):
    m = len(pattern)
    fail = [0] * m
    j = 0  # 最长前后缀的长度
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = fail[j - 1]  # 关键：利用已计算的 fail 值
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
    return fail
```

KMP 搜索

有了失败函数，搜索过程中不再回退文本指针 i，只调整模式指针 j：

python
def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    fail = build_fail(pattern)
    results = []
    j = 0  # 模式中当前匹配位置
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = fail[j - 1]  # 不回退 i，只调整 j
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            results.append(i - m + 1)
            j = fail[j - 1]  # 继续搜索下一个
    return results
```

关键性质：文本指针 i 从不回头。每次字符比较，i 要么前进，要么保持不动（j 回退）。可以证明 i 至多前进 n 次，j 的总回退量不超过 j 的总前进量（最多 n 次）。因此整个搜索是 $O(n)$，预处理是 $O(m)$，总体 $O(n + m)$。

换个视角：KMP 是一台自动机

失配函数的本质是把模式 P 编译成一台确定性自动机：状态就是"当前已匹配的最长前缀长度 j"（共 m+1 个状态），每个状态对每个可能的输入字符都有一条确定的转移——匹配则 j+1，失配则沿 fail 链落到正确的次长前缀。主循环里每读入一个字符恰好发生一次状态转移；"文本指针永不回退"的本质，是扫描被组织成了自动机的单向运行。

这个视角解释了 KMP 在流式数据上的独特优势：不需要缓存文本，字符边到达边匹配，内存占用与文本长度无关。预处理构建失配表之所以也是 $O(m)$，用的正是与主循环同一个摊还论证——j 的总前进不超过 m 次，故总回退也不超过 m 次。

Boyer-Moore 算法：从右往左，跳更远

同在 1977 年，罗伯特·博耶（Robert S. Boyer）和J·斯特罗瑟·摩尔（J. Strother Moore）提出了 Boyer-Moore 算法。它从不同方向出发，在实践中通常比 KMP 更快——因为它能跳过更多字符。

Boyer-Moore 有两个启发式规则，都基于"从模式右端开始比较"：

坏字符规则（Bad Character Rule）：当 T[i+j] 与 P[j] 不匹配时，在 P 中找 T[i+j] 最后一次出现的位置，把 P 向右对齐到那个位置。如果 T[i+j] 在 P 中根本不存在，直接跳过整个模式长度 m。

好后缀规则（Good Suffix Rule）：已匹配的后缀在 P 中其他位置再找找，对齐到下一个可能匹配的位置。

对于长模式和随机文本，Boyer-Moore 的平均复杂度是 $O(n/m)$——文本越长、模式越长，跳过的越多，速度越快。最坏情况是 $O(nm)$，但极少发生。

实践中，grep 命令使用的算法正是 Boyer-Moore 的变体——这就是为什么 grep "longpattern" huge_file.log 比预期快很多。多数文本编辑器与语言标准库采用的则是只保留坏字符规则的简化版（Horspool 变体）：放弃好后缀规则带来的最坏情况保证，换一张小得多的跳转表和更少的分支——平均场景下几乎不掉速。

Rabin-Karp：哈希加速

1987 年，迈克尔·拉宾（Michael Rabin）和理查德·卡普（Richard Karp）提出了一种完全不同的思路：用哈希函数加速比较。

思路：不直接比较 m 个字符，先比较哈希值。如果哈希值不同，绝对不匹配（跳过）；如果哈希值相同，再逐字符确认（避免哈希碰撞误报）。

关键技术是滚动哈希（Rolling Hash）：从 T[i..i+m-1] 滑动到 T[i+1..i+m] 时，只需 $O(1)$ 时间更新哈希值（而非重新计算整个窗口）：

h(T[i+1..i+m])=(h(T[i..i+m−1])−T[i]⋅bm−1)⋅b+T[i+m]h(T[i+1..i+m]) = \left(h(T[i..i+m-1]) - T[i] \cdot b^{m-1}\right) \cdot b + T[i+m]

（其中 b 是进制基数，通常取 256；计算在某个大素数模下进行）

Rabin-Karp 在多模式匹配中有独特优势：同时搜索 k 个模式，用哈希表把所有模式的哈希存起来，每次滑动窗口只需查一次哈希表，复杂度是 $O((n+m)k)$。这是病毒扫描软件同时查找数万种病毒签名的基础技术之一。

碰撞概率与生日悖论：滚动哈希把 $m$ 个字符压成一个 $b$ 位整数，碰撞不可避免。生日悖论指出：在 2b2^b 个可能的哈希值中随机取 $k$ 个，$k$ 接近 2b/22^{b/2} 时碰撞概率就不可忽略。10 GB 文本有约 101010^{10} 个窗口，而 32 位哈希只有约 4×1094\times10^9 个取值——假阳性不是小概率事件，而是必然大量发生。所以 Rabin-Karp 的哈希永远只是"筛子"：哈希相等必须逐字符确认。工程上要么用 64 位哈希把期望碰撞数压到可忽略，要么接受确认开销——反正确认只发生在哈希命中时，摊还代价仍是线性的。

算法对比

算法预处理搜索实践表现适用场景
暴力O(1)O(nm)差（短模式可用）极短文本
KMPO(m)O(n)稳定流式数据、DNA序列
Boyer-MooreO(m + σ)O(n/m) 平均最快（实践中）大文件搜索
Rabin-KarpO(m)O(n) 平均多模式最佳多模式匹配
Aho-CorasickO(Σm)O(n + 输出)多模式最强病毒扫描、内容过滤

（σ 为字母表大小，Σm 为所有模式总长度）

Aho-Corasick 算法（Alfred Aho 和 Margaret Corasick，1975）是 KMP 在多模式情况的推广——把所有模式构建成一个自动机（类似 Trie + KMP 失败函数），对文本扫描一遍即可找出所有模式的所有出现。UNIX 的 fgrep 命令使用此算法，入侵检测系统（IDS）的签名匹配引擎也大量使用它。

实践中的常数战争

教科书的大 O 排序与工程实现的快慢并不一致，字符串匹配是最典型的战场。

常数空间的线性算法：glibc 的 strstr 与 memmem——Linux 上几乎所有 C 程序字符串搜索的最终归宿——用的不是 KMP 也不是 Boyer-Moore，而是 Two-Way 算法（Crochemore & Perrin，1991）。它把模式在某个"关键分解点"切成两半，先正向比对右半、再反向比对左半，失配时的位移由分解点的组合性质直接给出。卖点不是平均速度，而是一个组合保证：最坏 $O(n)$ 时间 + $O(1)$ 额外空间。KMP 需要 $O(m)$ 的失配表，Boyer-Moore 需要字母表大小的跳转表——对一个被调用亿万次、输入完全不可控的库函数来说，"不占内存、没有病态输入"比平均快两成重要得多。

SIMD 让"暴力"复活：现代 CPU 的一条 SIMD 指令可以并行比较 16 或 32 个字节。对短模式（比如一个英文单词），"用 SIMD 扫文本找出首字符的候选位置、再逐字符确认"这种近乎暴力的策略，常数小到常常击败所有精巧算法——预处理、查表和分支预测失败都是有代价的。理论保证的是增长趋势，常数决定的是今天的速度；选哪个取决于模式长度、字母表大小与调用频率，而不是大 O 表格。

现实中的字符串匹配

DNA 序列比对：人类基因组有约 30 亿个碱基对。找到一个 1000 碱基的基因序列在哪里，需要极高效的字符串匹配。Burrows-Wheeler Alignment（BWA，2009）等工具把 BWT（Burrows-Wheeler 变换）与 FM-Index 结合，实现了亚线性时间的基因比对。

全文搜索引擎：Google、Elasticsearch 等搜索引擎并不实时做字符串匹配，而是预先建立倒排索引（Inverted Index）：每个词对应一个文档 ID 列表。搜索时直接查索引，不需要扫描文档。字符串匹配只在建立索引时和某些特殊查询（正则、通配符）时发生。

正则表达式引擎：正则表达式匹配可以通过 NFA/DFA 自动机实现（理论上 $O(nm)$ 或 $O(n)$），也可以用回溯方式实现（PCRE 等，某些情况下会指数级慢）。2019 年，Cloudflare 遭受了因 Web 应用防火墙使用的正则表达式发生"灾难性回溯"（catastrophic backtracking）而导致的全球性宕机，持续约 27 分钟。

代价与争议

理论最优与实践最优的背离：KMP 和 Boyer-Moore 的理论复杂度都是 $O(n)$，但在实践中（特别是英文文本），由于 Boyer-Moore 的跳跃效果，它通常快得多。理论上的大O分析在常数因子很大时会失真。

实现复杂度：Boyer-Moore 的正确实现（包含好后缀规则的完整版本）出了名地难写对。很多教程和实现只实现了坏字符规则（BM 的简化版），严格说来并不是完整的 Boyer-Moore 算法。

Unicode 的挑战：上述所有算法处理的是固定宽度的字节（ASCII）。Unicode 引入了变长编码（UTF-8：1–4 字节），多语言字符有时在视觉上等价但编码不同（如全角/半角、不同的空白字符），使字符串匹配在语义上更加复杂。

跨域连接

  • 自动机与形式语言：失败函数其实是把模式串编译成一台自动机，读文本时状态只前进不回退。多模式匹配把这一步推到极致：所有模式先合成一台机器，此后一遍扫描的代价与模式数量几乎无关。反过来，回溯式正则引擎正因为离开了自动机模型，才可能在某些输入上指数级变慢。
  • 哈希：滚动哈希让窗口右移一位时哈希值可以常数时间更新，从而把逐字符比较换成整数比较。代价是碰撞必须被复查，所以它天然是一个筛子而非判定器；也正因为筛子可以同时装很多模式，它在多模式场景里格外划算。
  • 基因测序：读段比对面对的是同一个文本被查询千万次的场景，逐次扫描不可行。把压缩变换与索引合一之后，查询代价只与读段长度有关，与基因组长度基本无关——这类工作的可行性来自索引，而不是来自匹配算法本身更快。
  • 文字系统类型：所有这些算法处理的是固定宽度的符号，而变长编码与附加符号让"字符"不再等于一个存储单元。在含变音符或组合成分的文字上，字节级匹配可能切在一个字符中间，于是正确性问题从算法转移到了规范化：先统一形式，再谈匹配。
  • AI 治理与监控：多模式自动机让匹配代价几乎与模式数量无关，只与流量和命中数有关。于是"检查全部流量"的边际成本趋近于零——技术上的规模不经济一旦消失，能不能扫与该不该扫就彻底分开了，约束只能来自制度而非算力。

参考文献

  • Knuth, D., Morris, J. & Pratt, V. Fast Pattern Matching in Strings. SIAM J. Comput. 6(2), 1977.（KMP 原始论文）
  • Boyer, R. & Moore, J. S. A Fast String Searching Algorithm. CACM 20(10), 1977.（BM 原始论文）
  • Crochemore, M. & Perrin, D. Two-Way String-Matching. Journal of the ACM 38(3), 1991.（glibc strstr/memmem 使用的算法）
  • Aho, A. & Corasick, M. Efficient String Matching: An Aid to Bibliographic Search. CACM 18(6), 1975.
  • Gusfield, D. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.（字符串算法最权威的教材）

正文中引用本条 · 4 · 其中 1 条来自其他领域

医学与公共卫生CRISPR 进入临床：当基因编辑第一次真正治好了一种病