WARNING

🧪 Beta公测版本提示：教程主体已完成，正在优化细节，欢迎大家提Issue反馈问题或建议。

algo13 字符串算法 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个练习题巩固字符串核心算法：KMP 的扩展应用、Trie 的高级操作、Manacher 的回文统计、滚动哈希的最长重复子串查找。

预备知识

• KMP 的 next 数组计算和匹配过程
• Trie 的插入、搜索和 DFS 遍历
• Manacher 的预处理和回文半径数组
• 滚动哈希的前缀哈希和 $O(1)$ 子串哈希查询

任务清单

任务1：KMP 统计重叠出现次数

• 关键点：KMP 的 k = next_arr[k] 机制天然支持重叠匹配的重叠计数。
• 实现：在 k == m-1 时计数器加 1，然后 k = next_arr[k] 继续。

任务2：Trie 的删除和最长公共前缀

• 删除：只需清除 is_end 标记（简化版）。完整版需要从叶子往回删除不再需要的节点。
• 最长公共前缀：从根出发，只要当前节点只有一个非空子节点（且当前节点不是单词结尾），就沿着该子节点继续。路径上的字符连接起来即为 LCP。

任务3：Manacher 统计回文子串

• 核心公式：R[i] 是以 T[i] 为中心的回文半径。在原串中，以 $i$ 为中心贡献的回文子串数为 $\lfloor (R[i]+1)/2\rfloor$。
• 对于原始串 s = "aaa"，扩展为 T = "#a#a#a#"，R = [0,1,2,3,2,1,0]，总和 = $1+1+2+1+1=6$。

任务4：最长重复子串

• 二分答案 + 滚动哈希：
  1. 二分搜索可能的子串长度 $L\in [1,n-1]$
  2. 对于给定的 $L$，用 RollingHash 计算所有长度为 $L$ 的子串哈希
  3. 用 set 检测是否有哈希冲突（即重复子串）
  4. 找到最大的可行 $L$ 后，返回对应的重复子串

提示

1. KMP 统计重叠匹配时，注意 next_arr[k] 不会越界（k=m-1 时回溯到 next[m-1]）。
2. Trie 的 LCP 查询复杂度 $O(min(len(wor{d}_i)))$。
3. Manacher 统计回文数时注意区分奇偶——但插入了 # 后就统一了。
4. 滚动哈希虽然概率正确，但在竞赛中通常足够（冲突概率 $\approx 1/M$，用 ${10}^9+7$ 和 ${10}^9+9$ 双哈希几乎不可能冲突）。

源码位置

clone 后打开（相对仓库根目录）：

docs/algorithms/topics/string/code/exercise.py