02.12.4 字符串进阶
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶
覆盖范围
- AC 自动机多模式匹配
- 后缀数组
- Manacher 最长回文
- 字符串哈希
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.12.4-001 | AC 自动机多模式匹配 | 高级 | ★★★ |
| 02.12.4-002 | AC 自动机构建 fail 指针 | 高级 | ★★★ |
| 02.12.4-003 | 后缀数组 SA 原理 | 高级 | ★★ |
| 02.12.4-004 | Manacher 最长回文 | 进阶 | ★★★★ |
| 02.12.4-005 | KMP 回顾与边界 | 基础 | ★★★★ |
| 02.12.4-006 | 字符串哈希 | 基础 | ★★★★ |
| 02.12.4-007 | AC 自动机 vs Trie | 基础 | ★★★ |
| 02.12.4-008 | 各算法复杂度对比 | 基础 | ★★★ |
02.12.4-001 AC 自动机多模式匹配
频率 ★★★ | 难度 高级
一句话结论
AC 自动机在 Trie 上建 fail 指针(类似 KMP 的 next),用于多模式匹配;文本扫描时失配自动跳到最长可匹配后缀;时间 O(n + m + z),n 为文本长,m 为模式串总长,z 为匹配次数。
概念解释
- Trie:所有模式串构建字典树。
- fail 指针:失配时跳到的节点,类似 KMP next。
- 多模式:一次扫描匹配所有模式串。
原理流程
- 构建 Trie。
- BFS 构建 fail 指针:根的子节点 fail 指向根;其他节点 fail = fail[父节点] 的子节点(同字符)。
- 扫描文本:从根出发,沿文本字符走;失配则跳 fail;走到终止节点则匹配。
代码 / 示例
class ACNode {
ACNode[] children = new ACNode[26];
ACNode fail;
boolean isEnd;
String word;
}
class AhoCorasick {
private final ACNode root = new ACNode();
void insert(String word) {
ACNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) node.children[idx] = new ACNode();
node = node.children[idx];
}
node.isEnd = true;
node.word = word;
}
void buildFail() {
java.util.Queue<ACNode> q = new java.util.ArrayDeque<>();
root.fail = root;
for (ACNode child : root.children) {
if (child != null) { child.fail = root; q.offer(child); }
}
while (!q.isEmpty()) {
ACNode u = q.poll();
for (int i = 0; i < 26; i++) {
ACNode v = u.children[i];
if (v != null) {
ACNode f = u.fail;
while (f != root && f.children[i] == null) f = f.fail;
v.fail = (f.children[i] != null && f.children[i] != v) ? f.children[i] : root;
q.offer(v);
}
}
}
}
java.util.List<String> search(String text) {
java.util.List<String> result = new java.util.ArrayList<>();
ACNode node = root;
for (char c : text.toCharArray()) {
int idx = c - 'a';
while (node != root && node.children[idx] == null) node = node.fail;
if (node.children[idx] != null) node = node.children[idx];
ACNode tmp = node;
while (tmp != root) {
if (tmp.isEnd) result.add(tmp.word);
tmp = tmp.fail;
}
}
return result;
}
}
常见误区
- 误区:fail 指针构建用 DFS;正解:用 BFS,保证父节点 fail 先构建。
- 误区:扫描时不跳 fail;正解:失配时必须跳 fail,才能匹配所有模式串。
追问 / 延伸
- Q:时间复杂度? A:O(n + m + z)。
- Q:AC 自动机用于什么? A:敏感词过滤、多模式匹配。
02.12.4-002 AC 自动机构建 fail 指针
频率 ★★★ | 难度 高级
一句话结论
fail[u] 表示 u 的最长可匹配后缀对应的 Trie 节点;BFS 构建:u 的子节点 v 的 fail = fail[u] 的同字符子节点(若不存在则继续跳 fail)。
概念解释
- fail[u]:u 的最长可匹配后缀。
- BFS 构建:按层构建,父节点 fail 先构建。
- 类似 KMP:fail 指针类似 next 数组。
原理流程
- 根的子节点 fail 指向根。
- BFS u:
- 对 u 的子节点 v(字符 c):
- f = fail[u]。
- while f != root 且 f.children[c] == null:f = f.fail。
- v.fail = f.children[c] != null ? f.children[c] : root。
代码 / 图示
fail[u] = u 的最长可匹配后缀
BFS 构建:
v = u.children[c]
f = fail[u]
while f != root && f.children[c] == null: f = f.fail
v.fail = f.children[c] != null ? f.children[c] : root
常见误区
- 误区:fail 构建用 DFS;正解:用 BFS。
- 误区:根的 fail 指向 null;正解:根的 fail 指向自己。
追问 / 延伸
- Q:fail 指针和 KMP next 区别? A:KMP next 是单模式,AC fail 是多模式(Trie 上)。
- Q:fail 指针链优化? A:可以把 fail 路径压缩,减少扫描时跳转。
02.12.4-003 后缀数组 SA 原理
频率 ★★ | 难度 高级
一句话结论
后缀数组 SA[i] 表示排第 i 的后缀的起始位置;rank[i] 表示后缀 i 的排名;height[i] 表示 SA[i] 和 SA[i-1] 的最长公共前缀;用倍增法 O(n log n) 构建。
概念解释
- SA[i]:排第 i 的后缀起始位置。
- rank[i]:后缀 i 的排名。
- height[i]:SA[i] 和 SA[i-1] 的 LCP。
- 倍增法:O(n log n) 构建。
原理流程
- 初始排名 = 字符。
- 倍增:每次按前 2^k 个字符排名,基数排序。
- 直到所有排名不同。
代码 / 图示
SA[i]:排第 i 的后缀起始位置
rank[i]:后缀 i 的排名
height[i]:SA[i] 和 SA[i-1] 的 LCP
常见误区
- 误区:SA 用快排;正解:快排 O(n^2 log n),倍增法 O(n log n)。
- 误区:height 直接计算;正解:height 用 O(n) 递推。
追问 / 延伸
- Q:SA 用于什么? A:最长重复子串、最长公共子串、后缀匹配。
- Q:时间复杂度? A:倍增法 O(n log n)。
02.12.4-004 Manacher 最长回文
频率 ★★★★ | 难度 进阶
一句话结论
Manacher 在每个字符间插特殊字符(如 #),统一奇偶;用 p[i] 记录以 i 为中心的回文半径;利用对称性避免重复计算,O(n) 求最长回文。
概念解释
- 插入 #:统一奇偶回文。
- p[i]:以 i 为中心的回文半径。
- 对称性:利用已知回文,减少重复计算。
原理流程
- 插入 #:s = "^#a#b#b#a#$"。
- 维护右边界 R 和中心 C。
- i 在 R 内:p[i] = min(p[2*C-i], R-i)。
- 中心扩展:i 为中心扩展回文。
- 更新 R 和 C。
代码 / 示例
String longestPalindrome(String s) {
StringBuilder t = new StringBuilder("^#");
for (char c : s.toCharArray()) t.append(c).append('#');
t.append('$');
int n = t.length();
int[] p = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
if (i < R) p[i] = Math.min(R - i, p[2 * C - i]);
while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) p[i]++;
if (i + p[i] > R) { C = i; R = i + p[i]; }
}
int maxLen = 0, center = 0;
for (int i = 0; i < n; i++) if (p[i] > maxLen) { maxLen = p[i]; center = i; }
return s.substring((center - maxLen) / 2, (center + maxLen) / 2);
}
常见误区
- 误区:不插入 #;正解:插入 # 统一奇偶回文。
- 误区:p[i] 初始为 0 不利用对称性;正解:i 在 R 内时 p[i] = min(R-i, p[2*C-i])。
追问 / 延伸
- Q:时间复杂度? A:O(n)。
- Q:Manacher vs 中心扩展? A:中心扩展 O(n^2),Manacher O(n)。
02.12.4-005 KMP 回顾与边界
频率 ★★★★ | 难度 基础
一句话结论
KMP 用 next 数组(前缀函数),失配时跳到 next 位置而不是从头开始;next[i] 表示模式串前 i 个字符的最长相等前后缀长度;时间 O(n+m)。
概念解释
- next[i]:前 i 个字符的最长相等前后缀长度。
- 失配:j = next[j-1],不是 j = 0。
- 时间:O(n+m)。
原理流程
- 构建 next 数组。
- 匹配:i 遍历文本,j 遍历模式串;失配时 j = next[j-1]。
代码 / 示例
int[] buildNext(String p) {
int[] next = new int[p.length()];
for (int i = 1, j = 0; i < p.length(); i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
if (p.charAt(i) == p.charAt(j)) j++;
next[i] = j;
}
return next;
}
int kmp(String text, String pattern) {
int[] next = buildNext(pattern);
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = next[j - 1];
if (text.charAt(i) == pattern.charAt(j)) j++;
if (j == pattern.length()) return i - j + 1;
}
return -1;
}
常见误区
- 误区:next 从 -1 开始;正解:Java 常用 0 开始。
- 误区:失配时 j = 0;正解:j = next[j-1]。
追问 / 延伸
- Q:KMP 时间复杂度? A:O(n+m)。
- Q:KMP 用于什么? A:单模式匹配。
02.12.4-006 字符串哈希
频率 ★★★★ | 难度 基础
一句话结论
字符串哈希把字符串映射成整数:hash(s) = s[0]*base^(n-1) + s[1]*base^(n-2) + ... + s[n-1];用前缀和 O(1) 求任意子串哈希;双哈希降低冲突。
概念解释
- base:进制,如 131 或 13331。
- 前缀哈希:h[i] = h[i-1]*base + s[i]。
- 子串哈希:h[r] - h[l-1]*base^(r-l+1)。
原理流程
- 预处理前缀哈希和 base 的幂。
- 子串 [l,r] 哈希 = h[r] - h[l-1]*base^(r-l+1)。
- 双哈希:两个不同 base 和 mod,降低冲突。
代码 / 示例
class StrHash {
private final long[] h, p;
private final int base = 131;
private final long mod = 1000000007;
StrHash(String s) {
int n = s.length();
h = new long[n + 1]; p = new long[n + 1];
p[0] = 1;
for (int i = 0; i < n; i++) {
h[i + 1] = (h[i] * base + s.charAt(i)) % mod;
p[i + 1] = (p[i] * base) % mod;
}
}
long query(int l, int r) { // 1-indexed
return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
}
常见误区
- 误区:子串哈希公式写错;正解:h[r] - h[l-1]*base^(r-l+1)。
- 误区:不用 mod;正解:不用 mod 会溢出,用 mod 或 unsigned long 自然溢出。
追问 / 延伸
- Q:哈希冲突怎么办? A:双哈希(两个 base 和 mod)。
- Q:字符串哈希用于什么? A:子串比较、回文判断、最长公共子串。
02.12.4-007 AC 自动机 vs Trie
频率 ★★★ | 难度 基础
一句话结论
Trie 是单模式/多模式字典树,但失配时只能从头开始;AC 自动机在 Trie 上建 fail 指针,失配时跳到最长可匹配后缀,实现多模式高效匹配。
概念解释
- Trie:字典树,前缀匹配。
- AC 自动机:Trie + fail 指针,多模式匹配。
- 区别:Trie 失配从头,AC 失配跳 fail。
原理流程
- Trie:插入模式串,扫描文本。
- AC 自动机:Trie + fail 指针,扫描时失配跳 fail。
代码 / 图示
Trie:
插入模式串
扫描文本,失配从头
AC 自动机:
Trie + fail 指针
扫描文本,失配跳 fail
常见误区
- 误区:Trie 就是 AC 自动机;正解:AC 自动机 = Trie + fail 指针。
- 误区:Trie 能做多模式匹配;正解:Trie 可以,但效率低,AC 自动机更高效。
追问 / 延伸
- Q:Trie 用于什么? A:前缀匹配、自动补全。
- Q:AC 自动机用于什么? A:敏感词过滤、多模式匹配。
02.12.4-008 各算法复杂度对比
频率 ★★★ | 难度 基础
一句话结论
KMP O(n+m),AC 自动机 O(n+m+z),Manacher O(n),字符串哈希 O(n) 预处理 O(1) 查询,后缀数组 O(n log n) 预处理 O(log n) 查询。
概念解释
- KMP:单模式匹配。
- AC 自动机:多模式匹配。
- Manacher:最长回文。
- 字符串哈希:子串比较。
- 后缀数组:后缀排序。
原理流程
见表格。
代码 / 图示
算法 预处理 查询 用途
KMP O(m) O(n) 单模式匹配
AC 自动机 O(m) O(n+z) 多模式匹配
Manacher - O(n) 最长回文
字符串哈希 O(n) O(1) 子串比较
后缀数组 O(n log n) O(log n) 后缀排序
常见误区
- 误区:KMP 是 O(n);正解:KMP 是 O(n+m),m 为模式串长度。
- 误区:Manacher 是 O(n^2);正解:Manacher 是 O(n)。
追问 / 延伸
- Q:现场写哪个? A:KMP、字符串哈希、Manacher 现场可写;AC 自动机和后缀数组一般不要求现场写。
- Q:怎么选? A:单模式 KMP,多模式 AC 自动机,子串比较哈希,回文 Manacher。
待整理清单
- [ ] 后缀自动机 SAM
- [ ] Z 算法
- [ ] 字符串哈希双哈希实现