算法模板 - 字符串
本文整理字符串相关的算法模板，按难度递增排列：朴素匹配 → KMP → Z 函数 → 字符串哈希 → AC 自动机。
1. 朴素字符串匹配
最简单的暴力匹配：逐个位置尝试，O(nm) 时间复杂度。虽然效率低，但代码极短，适合模式串很短或数据量小的场景。
什么时候用朴素匹配？ 当 n 和 m 都很小（< 1000），或者你需要快速验证某个匹配逻辑时，朴素匹配比 KMP 简单得多，不容易写错。
def naive_search(text: str, pattern: str) -> list:
"""暴力匹配，返回所有匹配位置的起始索引"""
n, m = len(text), len(pattern)
positions = []
for i in range(n - m + 1):
if text[i:i + m] == pattern:
positions.append(i)
return positions
# 示例
print(naive_search("ababaababaca", "abab")) # [0, 2, 6]朴素匹配为什么慢？ 因为每次匹配失败后，它只移动一位重新开始。大量比较是重复的——KMP 正是通过"记住已匹配的部分"来避免这些重复。
2. KMP 算法
KMP 是单模式串匹配的经典算法，O(n + m) 时间复杂度。核心是前缀函数——它告诉我们在匹配失败时，模式串应该"跳"到哪里继续匹配，避免从头开始。
2.1 前缀函数（π 函数）
定义：对于字符串 s 的第 i 个位置，π[i] 是满足 s[0..k-1] == s[i-k..i-1] 的最大 k（即 s[0..i] 的最长相等前后缀长度）。
直觉理解：π[i] 回答了这样一个问题——"以 s[i] 结尾的子串中，最长的、同时也是 s 的前缀的那个子串有多长？"
def prefix_function(s: str) -> list:
"""计算前缀函数，O(n)"""
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1] # 回退到更短的前缀
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
# 示例
print(prefix_function("ababab")) # [0, 0, 1, 2, 3, 4]
# 解读：π[4]=3 表示 s[0..4]="ababa" 的最长相等前后缀是 "aba"（长度 3）回退过程的理解：j = pi[j-1] 的含义是——如果当前位置不匹配，我们尝试用"次长的相等前后缀"继续匹配。这就像一个"弹性绳"，匹配失败时自动缩短。
为什么 O(n)？ 虽然有 while 循环，但 j 每次回退至少减少 1，而整个过程中 j 最多增加 n 次。所以总回退次数 ≤ 总增加次数 ≤ n。
2.2 KMP 匹配
巧妙做法：将 pattern + '#' + main_str 拼接，计算前缀函数。当 pi[i] == len(pattern) 时，说明找到了匹配。
def kmp_search(main_str: str, pattern: str) -> list:
"""返回 pattern 在 main_str 中所有出现位置的起始索引"""
m = len(pattern)
if m == 0 or m > len(main_str):
return []
combined = pattern + '#' + main_str
pi = prefix_function(combined)
return [i - 2 * m for i in range(m + 1, len(pi)) if pi[i] == m]
# 示例
print(kmp_search("ababaababaca", "abab")) # [0, 2, 6]
print(kmp_search("aaaaa", "aa")) # [0, 1, 2, 3]为什么加 '#'？ 分隔符确保 pattern 部分的前缀函数不会"溢出"到 main_str 部分。'#' 必须是一个不在 pattern 和 main_str 中出现的字符。
3. Z 函数
定义：Z[i] 表示从位置 i 开始的子串与原串前缀的最长匹配长度。与前缀函数"对偶"。
什么时候用 Z 函数？ 当你需要知道"从每个位置开始，和原串前缀匹配了多长"时，Z 函数比前缀函数更直观。
def z_function(s: str) -> list:
"""Z 函数（扩展 KMP），O(n)"""
n = len(s)
z = [0] * n
l, r = 0, 0 # [l, r] 是当前最右的匹配区间
for i in range(1, n):
if i <= r:
z[i] = min(z[i - l], r - i + 1) # 利用已知信息
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1 # 更新最右匹配区间
return z
# 示例
print(z_function("ababab")) # [0, 0, 4, 0, 2, 0]
# 解读：Z[2]=4 表示 s[2..]="abab" 与 s[0..]="ababab" 匹配了 4 个字符Z 函数 vs 前缀函数：
| 特性 | Z 函数 | 前缀函数 |
|---|---|---|
| 定义 | Z[i] = s[0..] 与 s[i..] 的最长匹配 | π[i] = s[0..i] 的最长相等前后缀 |
| 视角 | "从 i 开始能匹配多少" | "以 i 结尾最长的前缀是多少" |
| 用途 | 找 pattern 在 text 中的出现 | KMP 匹配、周期性分析 |
| 关系 | Z 和 π 是"对偶"的，可以互相转换 |
4. 字符串哈希
核心思想：把字符串映射为一个数字，使得 O(1) 时间内可以比较任意两个子串是否相等。本质是把字符串当成一个 B 进制数。
公式推导：
hash(s[0..r]) = s[0]*B^r + s[1]*B^(r-1) + ... + s[r]*B^0
hash(s[l..r]) = hash(s[0..r]) - hash(s[0..l-1]) * B^(r-l+1)MOD = 10 ** 9 + 7
base = 52
MX = 5000
# 预处理 base 的幂
f = [1] * (MX + 1)
for i in range(1, MX + 1):
f[i] = f[i - 1] * base % MOD
def hash_str(nums):
"""计算前缀哈希数组"""
n = len(nums)
h = [0] * (n + 1)
for i, x in enumerate(nums):
h[i + 1] = (h[i] * base + x + 1) % MOD
return h
def substr_hash(l, r, h):
"""计算子串 [l, r] 的哈希值（闭区间），O(1)"""
return (h[r + 1] - h[l] * f[r + 1 - l]) % MOD为什么用 x + 1 而不是 x？ 避免字符 'a'（值为 0）导致 "a" 和 "aa" 哈希相同。加 1 保证每个字符的贡献非零。
注意事项：
- 哈希碰撞概率极低但不为零。竞赛中通常用双哈希（两个不同的 base 和 MOD）进一步降低风险。
- base 通常选 131、13331、52 等质数。
- MOD 通常选 10^9+7 或 10^9+9。
5. AC 自动机
适用场景：多模式串匹配——同时在文本串中查找多个模式串的出现。可以理解为"Trie 上的 KMP"。
核心思想：先用所有模式串构建一棵 Trie，然后给每个节点加一个 fail 指针——当匹配失败时，沿着 fail 指针跳转到"最长后缀匹配"的位置，继续匹配。
from collections import deque, Counter
class AcTrieNode:
def __init__(self):
self.next = {} # 子节点
self.fail = None # fail 指针
self.is_end = False # 是否是某个模式串的结尾
self.word = "" # 如果 is_end，存储对应的模式串
self.fail_words = [] # fail 链上的所有结尾单词
class AcTrie:
def __init__(self):
self.root = AcTrieNode()
def insert(self, word: str):
"""插入一个模式串到 Trie"""
node = self.root
for ch in word:
if ch not in node.next:
node.next[ch] = AcTrieNode()
node = node.next[ch]
node.is_end = True
node.word = word
def build(self, words: list):
"""构建 AC 自动机（BFS 构建 fail 指针）"""
for word in words:
self.insert(word)
q = deque()
for child in self.root.next.values():
child.fail = self.root
q.append(child)
while q:
cur = q.popleft()
for ch, child in cur.next.items():
q.append(child)
# 从 cur 的 fail 指针开始，找最长的能匹配 ch 的后缀
p = cur.fail
while p and ch not in p.next:
p = p.fail
child.fail = p.next[ch] if p and ch in p.next else self.root
child.fail = child.fail if child.fail else self.root
# 继承 fail 链上的结尾单词
if child.fail.is_end:
child.fail_words.append(child.fail.word)
child.fail_words.extend(child.fail.fail_words)
def search(self, text: str, counter: Counter) -> int:
"""在 text 中搜索所有模式串，返回匹配总数"""
cur = self.root
matched = set()
result = 0
for ch in text:
while cur and ch not in cur.next:
cur = cur.fail
cur = cur.next[ch] if cur and ch in cur.next else self.root
# 检查当前节点和 fail 链上的所有结尾
if cur.is_end and cur.word not in matched:
matched.add(cur.word)
result += counter[cur.word]
for word in cur.fail_words:
if word not in matched:
matched.add(word)
result += counter[word]
return resultfail 指针的含义：从根到 fail 节点的路径，是当前节点对应字符串的最长真后缀，且这个后缀也是某个模式串的前缀。这和 KMP 的 next 数组本质相同，只是作用对象从字符串变成了 Trie。
总结
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 朴素匹配 | O(nm) | 暴力，模式串短时可用 |
| KMP（前缀函数） | O(n + m) | 单模式串匹配 |
| Z 函数 | O(n) | 前缀匹配、扩展 KMP |
| 字符串哈希 | O(1) 查询 | 子串比较、回文判断 |
| AC 自动机 | O(n + m + z) | 多模式串匹配 |
模板源码：AlgorithmLearning