字符串匹配、哈希与回文 · HTML
数学 / 逻辑形态
奇回文中心为 (i,i)，偶回文中心为 (i,i+1)；只要 s[l]==s[r] 就扩展半径。
识别信号
- 目标是连续回文子串
- 需要最长回文或回文个数
- n² 可接受且希望低额外空间
- 奇偶长度都要覆盖
- 回文由中心对称决定
容易误判的相似信号
| Signal | Why it is different |
|---|
| 回文子序列 | 子序列不连续，中心扩展会漏解，应使用 DP。 |
| 需要大量区间回文查询 | 重复中心扩展代价高，可用 DP、哈希或 Manacher 半径。 |
核心不变量
扩展循环开始时 s[l+1:r] 已是回文；端点相等后加入的新区间仍是回文。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前左右端点、最佳区间 best、可选的回文计数。 |
| Transition | 对每个奇偶中心分别扩展；每次成功更新答案，再 l--、r++。 |
| Frontier / order | 左右端点是对称前沿；首次不相等时该中心所有更大半径都不可能。 |
Python 骨架
def palindromes_by_center(s):
best = (0, 0)
count = 0
def grow(l, r):
nonlocal best, count
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
if r-l > best[1]-best[0]: best = (l, r)
l -= 1; r += 1
for i in range(len(s)):
grow(i, i)
grow(i, i+1)
l, r = best
return s[l:r+1], count
正确性思路
- 每个回文有唯一中心与半径。
- 算法枚举全部 2n-1 个奇偶中心。
- 对一个中心，扩展逐半径检查且首次失配后更大半径也失败。
- 因此每个回文恰被计数一次，最长者必被记录。
复杂度
| Time | Space | Parameters |
|---|
| 最坏 O(n²) | O(1) 不计输出 | n 为字符串长度；Manacher 可降至 O(n) |
边界条件
- 空串需要单独返回
- 单字符既是回文
- 偶回文中心在字符之间
- 相同最长答案需规定取最左或任意
- 全同字符触发最坏时间
错误模式
| Pattern | Why it fails / fix |
|---|
| 只枚举奇中心 | 会漏掉所有偶长度回文。 |
| 比较后才做边界检查 | 端点访问前必须确认合法。 |
| 把半径当长度 | 奇偶中心的长度公式不同，最好直接维护端点。 |
选择与排除规则
- n² 可接受且要清晰模板：中心扩展。
- 连续回文规模大：Manacher。
- 回文子序列：区间 DP。
- 大量动态回文查询：考虑哈希或专门结构。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最长回文为 aba，共有 5 个回文子串。 |
| Scenario | 字符串 abac。 |
| Walkthrough | 中心 b 扩展出 aba；四个单字符各贡献一个，其余中心首步失配。 |
Recall prompts
我的补充