字符串算法¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| next 手算 | next[i] = 前缀 P[0..i] 的最长相等真前后缀 | 掐头去尾对齐 |
| 失配移动 | 模式串滑到 next 位置续比，文本指针不动 | 文本不回头 |
| 最短循环节 | 长度 n、next[n−1] = d，且 (n−d) 整除 n → 循环节长 n−d | 减去 next |
| 子串哈希 | 前缀哈希差分取子串值，O(1) 比较 | 前缀差分 |
| Trie | 结点数 = 互异前缀 + 根；查前缀走 m 步 | 数前缀加根 |
KMP 的 next 数组¶
【是什么】 next[i] = 子串 P[0..i] 的最长相等真前后缀长度（真 = 不含整个串）。
【怎么算】 对每个位置，找掐掉首尾后能与开头对齐的最长长度。
【例】（2025 真题）P = "abacaba"：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| P[i] | a | b | a | c | a | b | a |
| next | 0 | 0 | 1 | 0 | 1 | 2 | 3 |
逐位解释：aba 首 a = 尾 a（1）；abacab 前缀 ab = 后缀 ab（2）；abacaba 前缀 aba = 后缀 aba（3）。
【失配移动】 匹配到 P[j] 失配时，模式串右滑、用 next[j-1] 位置的字符继续比较——已匹配前缀的后缀与模式串前缀相等，这段不用重比；文本指针全程不回退，总复杂度 \(O(n+m)\)。
循环节¶
【是什么】 串 S 由长度 L 的块重复若干次构成，L 最小者为最短循环节。
【怎么算】 \(L = n - next[n-1]\)；当 \(L \mid n\) 时整串恰由整数个块组成。
【例】 abcabcabc（n = 9）：next[8] = 6，\(L = 9 - 6 = 3\)，3 整除 9 → 循环节 abc。
字符串哈希与 Trie¶
- 哈希：把前缀
S[0..i]映射成多项式值 \(h_i\)，子串S[l..r]的哈希 = \(h_r - h_{l-1}\cdot B^{r-l+1}\)——O(1) 取值、O(1) 比子串相等；单哈希可能碰撞，双哈希（两组底数与模数）把冲突压到可忽略； - Trie：结点数 = 所有串的互异前缀数 + 1（根）；查某前缀是否存在沿边走 m 步；判“是否为已存串的前缀”是 Trie 的本职。
练习题目¶
练习 1 · next 定义¶
题目
KMP 中 next[i] 的定义是（ ）
- A. P[0..i] 的长度
- B. P[0..i] 的最长相等真前后缀长度
- C. 失配次数
- D. 字符的 ASCII 值
答案与解析
答案：B
“真”表示不能取整个串本身。
练习 2 · next 手算（aab）¶
题目
P = "aab" 的 next 数组是（ ）
- A.
{0, 0, 1} - B.
{0, 1, 1} - C.
{0, 1, 0} - D.
{1, 1, 0}
答案与解析
答案：C
a=0；aa 前后缀 a=a（1）；aab 无相等前后缀（0）。
练习 3 · next 手算（周期串）¶
题目
P = "aaaa" 的 next 数组是（ ）
- A.
{0, 0, 0, 0} - B.
{1, 2, 3, 4} - C.
{0, 1, 1, 1} - D.
{0, 1, 2, 3}
答案与解析
答案：D
前缀长 1、2、3 的 a 串都能与后缀对齐——全同一字符逐位加一。
练习 4 · next 手算（abab）¶
题目
P = "abab" 的 next 数组是（ ）
- A.
{0, 0, 1, 2} - B.
{0, 0, 1, 0} - C.
{0, 1, 1, 2} - D.
{0, 0, 0, 2}
答案与解析
答案：A
aba（1）；abab 前后 ab（2）——隔位上涨是 ab 交替串的形状。
练习 5 · next 手算（abcab）¶
题目
P = "abcab" 的 next 数组是（ ）
- A.
{0, 0, 0, 0, 1} - B.
{0, 0, 0, 1, 2} - C.
{0, 1, 1, 1, 2} - D.
{0, 0, 0, 1, 0}
答案与解析
答案：B
abca 首 a = 尾 a（1）；abcab 前 ab = 后 ab（2）。
练习 6 · next 手算（abcabd）¶
题目
P = "abcabd" 的 next 数组是（ ）
- A.
{0, 0, 0, 1, 2, 3} - B.
{0, 0, 0, 0, 1, 2} - C.
{0, 0, 0, 1, 2, 0} - D.
{0, 1, 0, 1, 2, 0}
答案与解析
答案：C
到 abcab 时 next = 2；末位 d 与前缀 ab 后继 c 不匹配，跌回 0。
练习 7 · next 手算（aabaab）¶
题目
P = "aabaab" 的 next 数组是（ ）
- A.
{0, 1, 0, 1, 2, 0} - B.
{0, 0, 0, 1, 2, 3} - C.
{0, 1, 1, 1, 2, 3} - D.
{0, 1, 0, 1, 2, 3}
答案与解析
答案：D
aab：前后缀 a（1）；aabaab 前后 aab（3）——小循环节串的 next 呈周期跳。
练习 8 · 失配跳转¶
题目
KMP 失配时下一步用 next 做什么（ ）
- A. 模式串滑到 next[失配位前一位] 对应位置继续比，文本指针不动
- B. 文本回退到开头
- C. 重新从头比
- D. 报错
答案与解析
答案：A
已匹配前缀的后缀信息复用——文本指针不回退是 \(O(n+m)\) 的关键。
练习 9 · KMP 复杂度¶
题目
KMP 匹配的总时间复杂度（ ）
- A. \(O(nm)\)
- B. \(O(n + m)\)
- C. \(O(n\log m)\)
- D. \(O(n^2)\)
答案与解析
答案：B
两个指针都只前进不回退（均摊分析）；\(O(nm)\) 是朴素逐位重比。
练习 10 · 朴素匹配最坏¶
题目
朴素（暴力）字符串匹配的最坏时间复杂度（ ）
- A. \(O(n + m)\)
- B. \(O(n\log n)\)
- C. \(O(nm)\)
- D. \(O(n)\)
答案与解析
答案：C
每个起点都可能比满 m 位（如 aaaaab 与 aab 型）——KMP 正是治这个的。
练习 11 · 最长相等真前后缀¶
题目
abcabc 的最长相等真前后缀长度是（ ）
- A. \(6\)
- B. \(0\)
- C. \(2\)
- D. \(3\)
答案与解析
答案：D
前 abc = 后 abc；6 是整个串不算“真”。
练习 12 · 循环节（整除）¶
题目
abcabcabc 的最短循环节长度是（ ）
- A. \(3\)
- B. \(9\)
- C. \(6\)
- D. \(1\)
答案与解析
答案：A
\(n - next[n-1] = 9 - 6 = 3\)，且 3 整除 9。
练习 13 · 循环节（不整除）¶
题目
长度 9、next[8] = 5 的串，\(n - next[n-1] = 4\) 不整除 9，说明（ ）
- A. 循环节是 9
- B. 整串不是周期串（4 只是“近似周期”）
- C. 无意义
- D. 串长必为 8
答案与解析
答案：B
只有 \(L = n - next[n-1]\) 整除 n 时才构成完整周期；否则只是前后缀的重叠。
练习 14 · 子串哈希¶
题目
字符串哈希把子串比较转化为（ ）
- A. 逐字符比较
- B. 排序
- C. 数值（前缀哈希差分）比较，O(1)
- D. 二分
答案与解析
答案：C
预处理前缀哈希后 O(1) 取任意子串哈希值。
练习 15 · 双哈希¶
题目
实战中用两组底数和模数做双哈希的目的是（ ）
- A. 加快一倍
- B. 节省内存
- C. 支持修改
- D. 降低哈希碰撞概率
答案与解析
答案：D
两组哈希同时碰撞才会误判——概率乘起来可忽略。
练习 16 · 哈希相等¶
题目
两个子串哈希值相等（单哈希）说明（ ）
- A. 极大概率相等，但不保证
- B. 一定相等
- C. 一定不等
- D. 无信息
答案与解析
答案：A
哈希是压缩映射，不同串可能同值（碰撞）；双哈希或直接比对兜底。
练习 17 · Trie 结点数¶
题目
将 he、she 插入空 Trie（含根），结点总数是（ ）
- A. \(5\)
- B. \(6\)
- C. \(4\)
- D. \(7\)
答案与解析
答案：B
互异前缀 h、he、s、sh、she 共 5，加根 = 6。
练习 18 · Trie 查找复杂度¶
题目
在 Trie 中查找一个长度为 m 的串，时间复杂度（ ）
- A. \(O(m \log \sigma)\)
- B. \(O(\text{串总数})\)
- C. \(O(m)\)
- D. \(O(m^2)\)
答案与解析
答案：C
每字符沿边走一步、共 m 步——与库里存了多少串无关。
练习 19 · Trie 判前缀¶
题目
判断某串是否为已有串的前缀，最适合（ ）
- A. 快速排序
- B. 并查集
- C. 堆
- D. Trie
答案与解析
答案：D
沿边走 m 步即知——Trie 天生存前缀。
练习 20 · Manacher¶
题目
Manacher 算法解决（ ）问题，复杂度（ ）
- A. 最长回文子串，\(O(n)\)
- B. 最长公共子序列，\(O(n\log n)\)
- C. 字符串匹配，\(O(n+m)\)
- D. 排序，\(O(n^2)\)
答案与解析
答案：A
利用已求回文的对称性线性扩展回文半径。
练习 21 · 回文判断¶
题目
下列是回文串的是（ ）
- A.
abcab - B.
abcba - C.
aabbc - D.
abcabc
答案与解析
答案：B
正读反读相同——双指针从两端向中间比对。
练习 22 · 子串计数¶
题目
长度为 n 的串按位置数的子串共（ ）个。
- A. \(2^n\)
- B. \(n^2\)
- C. \(\dfrac{n(n+1)}{2}\)
- D. \(n - 1\)
答案与解析
答案：C
起点终点各选一层求和；\(2^n\) 是子序列数。
练习 23 · 本质不同子串¶
题目
aaa 的本质不同子串有（ ）个。
- A. \(6\)
- B. \(1\)
- C. \(2\)
- D. \(3\)
答案与解析
答案：D
内容只有 a、aa、aaa 三种——按位置 6 个、按内容 3 个。
练习 24 · 子串 vs 子序列¶
题目
ac 对于 abc 是（ ）
- A. 子序列但不是子串
- B. 子串但不是子序列
- C. 都是
- D. 都不是
答案与解析
答案：A
保序跳选是子序列；不连续不是子串。
练习 25 · LCS 的解法¶
题目
最长公共子序列（LCS）的正确解法是（ ）
- A. 贪心取公共字符
- B. 二维 DP
- C. 排序后比对
- D. KMP
答案与解析
答案：B
失配时左/上两种取舍需要全子问题表——贪心不成立（KMP 管匹配不管公共子序列）。
练习 26 · 综合判断¶
题目
下列错误的是（ ）
- A. next 数组是模式串自身的性质
- B. Trie 的结点数等于互异前缀数加一
- C. KMP 最坏 \(O(nm)\)
- D. 子串哈希可 O(1) 比较子串相等
答案与解析
答案：C
KMP 最坏也是 \(O(n+m)\)；\(O(nm)\) 是朴素匹配。
历年真题¶
2025 年 · 第 2 题¶
题目
在 KMP 算法中，对于模式串 P="abacaba"，其 next 数组（next[i] 定义为模式串 P[0...i] 最长公共前后缀的长度，且数组下标从 \(0\) 开始）的值是什么？
- A.
{0, 0, 1, 0, 1, 2, 3} - B.
{0, 1, 2, 3, 4, 5, 6} - C.
{0, 0, 1, 1, 2, 2, 3} - D.
{0, 0, 0, 0, 1, 2, 3}
答案与解析
答案：A
逐位求最长相等真前后缀（完整表格见教学节）：a0、ab0、aba1、abac0、abaca1、abacab2、abacaba3。
易错小结¶
- next 是模式串自身的最长相等真前后缀（2025 真题
{0,0,1,0,1,2,3}）；全同串逐位 +1、ab 交替隔位涨； - 失配跳 next、文本指针不回退 → KMP \(O(n+m)\)；朴素匹配最坏才 \(O(nm)\)；
- 最短循环节 \(n - next[n-1]\)，整除 n 才是真周期；
- 子串哈希 O(1) 比较、双哈希防碰撞；Trie 结点 = 互异前缀 + 根；
- 子串（连续）与子序列（保序跳选）区分；LCS 是二维 DP，不是 KMP 也不是贪心。