字符串算法

字符串问题族的三个层次：单模式匹配（KMP）、多模式匹配（AC 自动机）、全后缀结构（后缀数组）。本章讲它们的原理，以及正则引擎的两种实现及其性能差异。

单模式匹配：KMP

朴素匹配 $O(nm)$ ：每次失配回退到起点重来。**KMP 的失配函数（failure function / next）**让模式串"自己匹配自己"预处理出：失配时模式串指针跳到哪里——跳到"已匹配部分的最长相等真前缀与后缀"处，不回退文本指针。 $O(n + m)$ 。

def kmp(text, pat):
    m = len(pat)
    fail = [0] * m
    k = 0
    for i in range(1, m):               # 预处理失配函数
        while k and pat[i] != pat[k]:
            k = fail[k - 1]
        if pat[i] == pat[k]:
            k += 1
        fail[i] = k

    k = 0
    for i, c in enumerate(text):        # 匹配：文本指针不回退
        while k and c != pat[k]:
            k = fail[k - 1]
        if c == pat[k]:
            k += 1
        if k == m:
            yield i - m + 1
            k = fail[k - 1]

KMP 的核心是"前缀的后缀"：失配函数本质是模式串每个前缀的"最长相等真前后缀"长度。Z 算法是等价的另一种表述（每个后缀与模式串的最长公共前缀），写起来更直。Rabin-Karp 用滚动哈希：指纹相等再逐字符确认，让子串比较 $O(1)$ ，多模式时（比较哈希集合）与二维匹配有用。

多模式匹配：AC 自动机

在文本中同时找 $k$ 个模式串：建字典树 + 失配指针 = AC 自动机，一次扫描 $O(n + \text{匹配数})$ 。敏感词过滤、入侵检测的基础（→ 并查集与字典树）。

全后缀结构：后缀数组

后缀问题的通用结构。后缀数组：所有后缀按字典序排序的下标数组（ $O(n \log n)$ 倍增或 DC3 线性构造），配合 LCP 数组（相邻后缀的最长公共前缀）：

子串查找：二分后缀数组， $O(m \log n)$ ；
最长重复子串：LCP 数组的最大值；
不同子串计数： $n(n+1)/2 - \sum \text{LCP}$ 。

后缀自动机是等价的更紧凑结构（ $O(n)$ 状态），实现复杂但一次构建回答所有子串问题。文本编辑器（大文件的重复检测）、生物信息（DNA 序列匹配）的基础。

正则表达式引擎

两种实现路线，性能天差地别（→ 有限自动机与正则语言）：

NFA 模拟（Thompson）：把正则编译成 NFA，同时模拟所有活跃状态—— $O(nm)$ 最坏有保证，与回溯无关。RE2 与 Rust regex 用它。
回溯（backtracking）：递归尝试、失败回退——实现简单、支持捕获组与反向引用，但存在指数级最坏情况（ReDoS）：(a+)+b 对 "aaaaaaaaaaaaaaaaaaaaX" 让引擎指数爆炸。多数语言内置引擎（PCRE、Python re、JS RegExp）是回溯式。

工程结论：处理不可信输入的正则用 NFA 式引擎（RE2）或加超时；回溯式引擎的正则要审查嵌套量词。这是"回溯式正则引擎存在指数级最坏情况"的实际形态——服务被一条正则打挂。

本章要点

KMP 的失配函数 = 每个前缀的"最长相等真前后缀"；文本指针不回退， $O(n+m)$
滚动哈希让子串比较 $O(1)$ ；AC 自动机 = 字典树 + 失配指针，多模式一次扫描
后缀数组 + LCP 回答所有后缀问题；后缀自动机更紧凑
NFA 模拟最坏 $O(nm)$ 有保证；回溯式引擎有 ReDoS 风险，不可信输入要防