String Algorithms
字符串算法常常出现在算法竞赛中，我们单独来看一下。
包括：
- pattern matching（模式匹配）
- string searching（字符串搜索）
- substring algorithms（子串算法）
- string hashing（字符串哈希）
- suffix array / suffix tree algorithms（后缀数组 / 后缀树算法）
基础字符串算法：反转字符串
高级字符串算法：
- KMP、Z-algorithm、
- AC 自动机（多模式匹配）
- 后缀数组 / 后缀自动机相关算法
- Boyer–Moore、Sunday 算法等高级字符串匹配
Manacher算法
Manacher算法是针对最长回文子串这一特定任务而实现的算法，其本质上就是以空间换时间，记录已经探索的信息并加以利用。
问题： 给定字符串 \(s\)，找出其中最长的回文子串。暴力做法是 \(O(n^2)\) 甚至 \(O(n^3)\)，Manacher可以做到 \(O(n)\)。
核心思路： 维护三个关键信息：
- 每个已探索位置的回文半径 \(p[i]\)（探索就是向两边扩张判断是否对称）
- 当前最右回文的中心点 \(c\)
- 当前已知回文能达到的最右边界 \(r\)
预处理： 为了统一处理奇偶长度的回文，在每个字符之间以及首尾插入特殊字符（如 #），将字符串变为奇数长度。例如 aba 变为 #a#b#a#，abba 变为 #a#b#b#a#。
算法步骤：
- 对原串做预处理，得到新串 \(t\)
- 维护数组 \(p[i]\) 表示以 \(t[i]\) 为中心的回文半径（不含中心本身）
- 遍历每个位置 \(i\)： - 如果 \(i < r\)（在已知最右回文范围内），则利用对称性：令 \(i' = 2c - i\)（\(i\) 关于 \(c\) 的镜像点），初始化 \(p[i] = \min(p[i'], r - i)\) - 否则 \(p[i] = 0\) - 然后尝试向两边扩展，若两侧字符相等则 \(p[i]\) 加 1 - 若 \(i + p[i] > r\)，则更新 \(r = i + p[i]\)，\(c = i\)
- 找到 \(p\) 数组中的最大值，即为最长回文的半径，反推出原串中的位置
关键优化点： 当 \(i\) 在已知回文范围 \([c - r, c + r]\) 内时，镜像点 \(i'\) 的回文信息可以直接复用，避免了大量重复比较。
def manacher(s: str) -> str:
# 预处理：插入 '#'
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n # p[i] = 以 t[i] 为中心的回文半径
c = r = 0 # 当前最右回文的中心和右边界
for i in range(n):
# 利用对称性初始化
if i < r:
mirror = 2 * c - i
p[i] = min(p[mirror], r - i)
# 尝试扩展
while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
and t[i + p[i] + 1] == t[i - p[i] - 1]):
p[i] += 1
# 更新最右边界
if i + p[i] > r:
c, r = i, i + p[i]
# 找最大回文半径
max_len = max(p)
center = p.index(max_len)
# 从变换串的位置还原到原串
start = (center - max_len) // 2
return s[start : start + max_len]
时间复杂度： \(O(n)\)，每个字符最多被扩展访问一次。空间复杂度： \(O(n)\)。
单模式精确匹配
KMP
问题： 在文本 \(T\)（长度 \(n\)）中查找模式串 \(P\)（长度 \(m\)）的所有出现位置。朴素做法需要 \(O(nm)\)，KMP将其优化到 \(O(n + m)\)，是理论最经典的单模式精确匹配算法。
核心思想：前缀函数（Prefix Function / Failure Function / next数组）
当匹配过程中发生失配时，朴素算法会把模式串右移一位，从头开始重新比较。KMP的关键洞察是：失配时，模式串已匹配的部分包含了有用的信息，可以利用这些信息跳过不可能成功的对齐位置。
前缀函数 \(\pi[i]\) 的定义：对于模式串 \(P\) 的前 \(i+1\) 个字符构成的子串 \(P[0..i]\)，\(\pi[i]\) 是其最长的、既是前缀又是后缀的真子串的长度。
例如对于 $P[0..i] = $ ABCAB，前缀有 A, AB, ABC, ABCA，后缀有 B, AB, CAB, BCAB，最长公共前后缀是 AB，所以 \(\pi[4] = 2\)。
前缀函数为什么能避免冗余比较？
当 \(P[j]\) 与 \(T[i]\) 失配时，我们已经知道 \(P[0..j-1]\) 与 \(T[i-j..i-1]\) 是匹配的。\(\pi[j-1]\) 告诉我们 \(P[0..j-1]\) 的最长公共前后缀长度为 \(\pi[j-1]\)，这意味着 \(P[0..\pi[j-1]-1]\) 已经和 \(T\) 中当前位置前面的字符对齐了，可以直接从 \(P[\pi[j-1]]\) 继续比较，而不是从 \(P[0]\) 重新开始。
构建前缀函数的算法：
def build_prefix_function(pattern: str) -> list[int]:
"""构建 KMP 前缀函数（next数组）"""
m = len(pattern)
pi = [0] * m # pi[0] 始终为 0
length = 0 # 当前最长公共前后缀的长度
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
pi[i] = length
i += 1
else:
if length != 0:
# 回退：利用已有的前缀函数信息
length = pi[length - 1]
# 注意这里不递增 i
else:
pi[i] = 0
i += 1
return pi
构建过程详解（Worked Example）：
以模式串 $P = $ ABABAC 为例，逐步构建前缀表 \(\pi\)：
| \(i\) | \(P[0..i]\) | 最长公共前后缀 | \(\pi[i]\) | 说明 |
|---|---|---|---|---|
| 0 | A |
（无真子串） | 0 | 单个字符，\(\pi[0]\) 恒为 0 |
| 1 | AB |
无匹配 | 0 | 前缀 A 与后缀 B 不同 |
| 2 | ABA |
A |
1 | 前缀 A = 后缀 A |
| 3 | ABAB |
AB |
2 | 前缀 AB = 后缀 AB |
| 4 | ABABA |
ABA |
3 | 前缀 ABA = 后缀 ABA |
| 5 | ABABAC |
无匹配 | 0 | P[5]='C'，回退到 pi[2]=1，再比 P[1]='B' != 'C'，再回退到 pi[0]=0，P[0]='A' != 'C'，最终为 0 |
最终前缀表：\(\pi = [0, 0, 1, 2, 3, 0]\)
KMP搜索算法：
def kmp_search(text: str, pattern: str) -> list[int]:
"""KMP搜索：返回 pattern 在 text 中所有出现的起始位置"""
n, m = len(text), len(pattern)
if m == 0:
return []
pi = build_prefix_function(pattern)
result = []
j = 0 # pattern 中的指针
for i in range(n): # text 中的指针
while j > 0 and text[i] != pattern[j]:
j = pi[j - 1] # 利用前缀函数回退
if text[i] == pattern[j]:
j += 1
if j == m:
result.append(i - m + 1) # 找到一个匹配
j = pi[j - 1] # 继续搜索下一个匹配
return result
复杂度分析：
- 构建前缀函数：\(O(m)\)
- 搜索阶段：\(O(n)\)
- 总时间复杂度：\(O(n + m)\)
- 空间复杂度：\(O(m)\)（存储前缀函数数组）
Boyer-Moore系
Boyer-Moore（BM）及其变体 Horspool、Sunday 是工程实践中最常用的单模式匹配算法。虽然最坏情况不一定优于 KMP，但在实际文本中通常远快于 KMP，因为它们能跳过更多的字符。
Boyer-Moore 核心思想
BM算法的匹配方向与KMP相反：从模式串的末尾（右端）向前比较。当发生失配时，利用两条规则计算模式串可以向右滑动的距离：
1. 坏字符规则（Bad Character Rule）：
当文本中的字符 \(T[i]\) 与模式串 \(P[j]\) 失配时，查看 \(T[i]\) 在模式串中最后一次出现的位置 \(k\)：
- 如果 \(T[i]\) 不在模式串中，整个模式串可以滑过 \(T[i]\)，移动距离为 \(j + 1\)
- 如果 \(T[i]\) 在模式串中且 \(k < j\)，将模式串右移使 \(P[k]\) 对齐 \(T[i]\)，移动距离为 \(j - k\)
- 如果 \(k > j\)，则该规则给出的移动距离为负数，此时至少移动 1
2. 好后缀规则（Good Suffix Rule）：
当部分匹配 \(P[j+1..m-1]\) 已经成功但 \(P[j]\) 失配时，在模式串中寻找另一处与已匹配后缀相同的子串，将其对齐。如果找不到完整的，则寻找已匹配后缀的最长后缀恰好等于模式串的某个前缀的情况。
实际滑动距离取两条规则的较大值。
为什么BM在实际中更快？
对于自然语言文本（字母表较大），坏字符规则经常能一次跳过很多位置。BM的最佳情况复杂度为 \(O(n/m)\)，即亚线性——不需要检查文本中的每个字符。
Horspool 简化版
Horspool算法是BM的简化版本，只使用坏字符规则，且始终根据当前窗口最右端对应的文本字符来决定移动距离。实现简单，实际效果接近完整BM。
def horspool_search(text: str, pattern: str) -> list[int]:
"""Horspool算法：BM的简化版，只用坏字符规则"""
n, m = len(text), len(pattern)
if m == 0 or m > n:
return []
# 构建坏字符表：每个字符到模式串末尾的距离
# 默认移动距离为 m（字符不在模式串中）
bad_char = {}
for i in range(m - 1): # 注意：不包括最后一个字符
bad_char[pattern[i]] = m - 1 - i
result = []
i = 0 # 窗口左端在 text 中的位置
while i <= n - m:
j = m - 1 # 从模式串末尾开始比较
while j >= 0 and text[i + j] == pattern[j]:
j -= 1
if j < 0:
result.append(i) # 完全匹配
# 移动窗口
i += bad_char.get(text[i + m - 1], m)
else:
# 根据窗口最右端对应的文本字符决定移动距离
i += bad_char.get(text[i + m - 1], m)
return result
Sunday 算法
Sunday算法比Horspool更进一步：失配时不看窗口内的字符，而是看当前窗口之后的第一个字符（即 \(T[i + m]\)）来决定移动距离。
- 如果 \(T[i + m]\) 不在模式串中，窗口直接跳过 \(m + 1\) 个位置
- 如果 \(T[i + m]\) 在模式串中，将模式串中该字符的最右出现位置与 \(T[i + m]\) 对齐
Sunday算法实现极其简单，在字母表较大、模式串较长时效果极佳。
复杂度对比
| 算法 | 最佳 | 平均 | 最坏 | 空间 | 特点 |
|---|---|---|---|---|---|
| KMP | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(m)\) | 理论保证，不回溯文本指针 |
| Boyer-Moore | \(O(n/m)\) | \(O(n)\) | \(O(nm)\) | \(O(m + \|\Sigma\|)\) | 实践最快，双规则 |
| Horspool | \(O(n/m)\) | \(O(n)\) | \(O(nm)\) | \(O(\|\Sigma\|)\) | BM简化版，只用坏字符 |
| Sunday | \(O(n/m)\) | \(O(n)\) | \(O(nm)\) | \(O(\|\Sigma\|)\) | 看窗口后一位，实现最简 |
其中 \(\|\Sigma\|\) 为字母表大小。在最坏情况下（如 $T = $ aaa...a，$P = $ aaa...ab），BM系列退化为 \(O(nm)\)，而KMP始终保持 \(O(n)\)。但在实际应用中，BM系列通常比KMP快 3-5 倍。
Two-Way
Two-Way算法是现代工业级字符串搜索的首选，许多标准库的底层实现都使用了这个算法，包括 glibc 的 strstr、Python 的 str.find / in 运算符、以及 Rust 的字符串搜索。
核心思想：结合KMP与BM的优势
Two-Way算法由 Crochemore 和 Perrin 于 1991 年提出，其关键思想是将模式串分成两部分（临界分解，Critical Factorization），然后：
- 右半部分从左到右比较（类似KMP的方向）
- 左半部分从右到左比较（类似BM的方向）
先比较右半部分，匹配后再验证左半部分。如果右半部分失配，利用类似KMP前缀函数的信息来决定移动距离。
为什么标准库选择Two-Way？
| 特性 | KMP | BM | Two-Way |
|---|---|---|---|
| 时间复杂度 | \(O(n + m)\) | 最坏 \(O(nm)\) | \(O(n + m)\) |
| 空间复杂度 | \(O(m)\) | \(O(m + \|\Sigma\|)\) | \(O(1)\) |
| 实际性能 | 一般 | 很快 | 快 |
Two-Way的最大优势在于只需要 \(O(1)\) 的额外空间（不需要像KMP那样预先分配 \(O(m)\) 的前缀表），同时保持 \(O(n + m)\) 的最坏情况时间复杂度保证。这使得它在内存敏感的系统库中非常理想——标准库不能假设模式串很短，\(O(m)\) 的空间开销在模式串很长时可能不可接受。
算法概要（概念性描述）：
- 临界分解： 找到模式串的一个分割点 \(\ell\)，将 \(P\) 分为 \(P[0..\ell-1]\) 和 \(P[\ell..m-1]\)，使得该分割满足"临界分解定理"的条件
- 右半部分匹配： 从 \(P[\ell]\) 开始向右逐字符与文本比较
- 左半部分验证： 如果右半部分全部匹配，再向左验证 \(P[0..\ell-1]\)
- 移动规则： 失配时根据模式串的周期性质计算移动距离，保证 \(O(1)\) 空间下的高效跳转
由于实现细节涉及临界分解定理和模式串周期分析，代码较为复杂，此处不展开完整实现。有兴趣的读者可参考 glibc 源码中的 str-two-way.h。
多模式匹配
比如有10万个敏感词，在一个文本里同时查。
Aho-Corasick
AC自动机（Aho-Corasick Automaton），多模式匹配的绝对统治者。
问题： 给定一组模式串集合 \(\{P_1, P_2, \ldots, P_k\}\) 和一个文本 \(T\)，同时在 \(T\) 中找出所有模式串的出现位置。如果用KMP逐个搜索，时间为 \(O(k \cdot (n + m_i))\)，当模式串数量很大时效率很低。AC自动机可以一次扫描文本就找到所有模式串的匹配。
核心思想：Trie + 失败指针（Failure Links）
AC自动机本质上是在Trie树上做KMP。KMP的前缀函数作用于单个模式串，而AC自动机将这个思想推广到了Trie上：
- Trie负责组织所有模式串的前缀结构
- 失败指针（failure link）类比KMP的前缀函数，指向当前状态的最长真后缀中同时也是某个模式串前缀的状态
构建过程：
- 建Trie： 将所有模式串逐个插入Trie树
- 建失败指针（BFS）： 从Trie的根节点开始BFS，对每个节点 \(u\)，其子节点 \(v\)（边字符为 \(c\)）的失败指针指向 \(u\) 的失败指针沿 \(c\) 走到的节点。根的所有直接子节点的失败指针指向根
- 搜索： 用一个指针在AC自动机上沿文本字符移动，每到一个节点就沿着失败指针链检查是否有模式串在此结束
时间复杂度： \(O(\sum|P_i| + |T| + \text{匹配数})\)，即所有模式串长度之和（建Trie） + 文本长度（搜索） + 输出匹配的数量。
典型应用：
- 敏感词过滤： 互联网内容审核中，将数万个敏感词构建为AC自动机，对每条用户输入做一次扫描即可检出所有敏感词
- 病毒特征码匹配： 杀毒软件用AC自动机在文件中同时搜索大量病毒签名
- 基因序列分析： 在DNA序列中同时搜索多个已知基因片段
- 入侵检测系统（IDS）： 网络流量中匹配攻击特征
Python实现：
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self):
# goto 函数：goto[state][char] -> next_state
self.goto = [{}]
# 失败指针
self.fail = [0]
# 输出函数：每个状态对应的模式串列表
self.output = [[]]
self.state_count = 0
def _new_state(self):
self.state_count += 1
self.goto.append({})
self.fail.append(0)
self.output.append([])
return self.state_count
def add_pattern(self, pattern: str, index: int = 0):
"""将一个模式串插入 Trie"""
state = 0
for ch in pattern:
if ch not in self.goto[state]:
self.goto[state][ch] = self._new_state()
state = self.goto[state][ch]
self.output[state].append((pattern, index))
def build(self):
"""BFS 构建失败指针"""
queue = deque()
# 根节点的直接子节点，失败指针指向根
for ch, s in self.goto[0].items():
self.fail[s] = 0
queue.append(s)
# BFS
while queue:
u = queue.popleft()
for ch, v in self.goto[u].items():
queue.append(v)
# 沿着 u 的失败指针找到能接受 ch 的状态
f = self.fail[u]
while f != 0 and ch not in self.goto[f]:
f = self.fail[f]
self.fail[v] = self.goto[f].get(ch, 0)
# 如果失败指针指向自己就修正为根
if self.fail[v] == v:
self.fail[v] = 0
# 合并输出：继承失败指针对应状态的输出
self.output[v] = self.output[v] + self.output[self.fail[v]]
def search(self, text: str) -> list[tuple[int, str]]:
"""在文本中搜索所有模式串，返回 (位置, 模式串) 列表"""
results = []
state = 0
for i, ch in enumerate(text):
# 沿失败指针寻找能接受 ch 的状态
while state != 0 and ch not in self.goto[state]:
state = self.fail[state]
state = self.goto[state].get(ch, 0)
# 收集当前状态的所有输出
for pattern, idx in self.output[state]:
pos = i - len(pattern) + 1
results.append((pos, pattern))
return results
# 使用示例
if __name__ == "__main__":
ac = AhoCorasick()
patterns = ["he", "she", "his", "hers"]
for i, p in enumerate(patterns):
ac.add_pattern(p, i)
ac.build()
text = "ahishers"
matches = ac.search(text)
for pos, pat in matches:
print(f"位置 {pos}: '{pat}'")
# 输出：
# 位置 1: 'his'
# 位置 3: 'she'
# 位置 4: 'he'
# 位置 4: 'hers'
AC自动机 vs 朴素多模式搜索：
假设有 \(k\) 个模式串，总长度为 \(M = \sum|P_i|\)，文本长度为 \(n\)：
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
| 逐个KMP | \(O(k \cdot n + M)\) | 需要扫描文本 \(k\) 次 |
| AC自动机 | \(O(M + n + z)\) | 只需扫描文本 1 次，\(z\) 为匹配数 |
当 \(k\) 很大时（如 10 万个敏感词），AC自动机的优势是压倒性的。