CSP暑期集训 Day 02 - 字符串专题

DAY 02

字符串专题

CSP 暑期集训 · 算法进阶 · 四大核心算法详解

#️⃣

字符串 Hash

进制映射 → 前缀和 → O(1)子串查询

🔄

Manacher 马拉车

回文半径 → 镜像加速 → O(n)线性

🔍

KMP 算法

next数组 → 最长公共前后缀 → O(n+m)

🌲

字典树 Trie

前缀树 → 逐字符插入 → O(|s|)查询

✏️ 📎

🎯 核心问题
给定 n 个字符串 S₁, S₂, ..., Sₙ，需要快速回答 m 个询问："字符串 T 是否出现过？"或者"子串 S[l..r] 和 S[l'..r'] 是否相同？"
字符串比较的代价是 O(长度)，当字符串很多时，暴力做法极慢。

暴力做法：逐字符比较

对于每个询问，逐一与所有已知字符串进行逐字符比较。

优化思路：把字符串变成数字

1

字符串

→

Hash

Hash函数

→

整数

唯一指纹

→

O(1)

比较整数

方案	暴力比较	Hash比较
原理	逐字符对比，不同即停	映射为整数，比较整数
单次比较	O(m) 最坏	O(1)
总时间	O(n × m)	O(n × m)预处理 + O(n)查询
子串查询	需重新逐字符比较	预处理后 O(1) 取任意子串

💡 关键问题：怎么设计一个好的 Hash 函数？需要满足：① 不同字符串映射到不同整数（无冲突）；② 计算速度快；③ 值域可控。

类比：十进制数的构成

十进制数 365 的构成：

365 = 3 × 10² + 6 × 10¹ + 5 × 10⁰

每个"数位"乘以对应的"权重"（10的幂次），然后求和。
类似地，我们可以把字符串的每个字符看成"B进制"的一个数位！

字符串的进制映射

定义：对于字符串 s = s₁s₂s₃...sₙ，选定基数 B（常用 131 或 13331），定义：

H(s) = s₁ × Bⁿ⁻¹ + s₂ × Bⁿ⁻² + ... + sₙ₋₁ × B¹ + sₙ × B⁰

其中 sᵢ 取字符的 ASCII 码值（如 'a'=97, 'b'=98...）

逐步代入计算：s = "abcde"，B = 131

递推形式（关键！）

不展开，用递推更高效：

H(s[1..1]) = s₁

H(s[1..2]) = H(s[1..1]) × B + s₂

H(s[1..3]) = H(s[1..2]) × B + s₃

H(s[1..i]) = H(s[1..i-1]) × B + sᵢ ← 递推公式！

验证： H(s[1..2]) = 97 × 131 + 98 = 12,707 + 98 = 12,805
H(s[1..3]) = 12,805 × 131 + 99 = 1,677,455 + 99 = 1,677,554 ✓
每一步只需一次乘法和一次加法，O(n) 即可完成！

💡 为什么 B 取 131 或 13331？经验值。131 是质数，足够大使得不同字符组合不容易碰撞。避免取偶数（如2的幂）或太小的数（如3、7），实验表明冲突率极低。

📐 Hash 前缀和数组 h[]
h[i] = H(s[1..i])，即前 i 个字符组成的子串的 Hash 值。
类比数组前缀和：sum[i] = sum[i-1] + a[i] ↔ h[i] = h[i-1] × B + s[i]

逐步计算：s = "abcde"，B = 131

核心代码

// 计算Hash前缀和数组
const int B = 131;
unsigned long long h[N], pw[N]; // h[]=前缀和, pw[]=B的幂次

pw[0] = 1;
for (int i = 1; i <= len; i++) {
    h[i] = h[i-1] * B + s[i];  // 递推！旧指纹"放大"B倍再加新字符
    pw[i] = pw[i-1] * B;        // 预计算B^i，后面子串查询要用
}

🔑 记忆口诀：h[i] = h[i-1] × B + s[i]，就像"滚动窗口"不断往右扩展！pw[i] = pw[i-1] × B 记录 B 的幂次。

🎯 目标：已知 h[1..n]，如何 O(1) 求出 H(s[l..r])？
这是字符串 Hash 最强大的能力——预处理后任意子串的指纹可 O(1) 取出。

数学推导（逐步展开）

第一步：展开 h[r]（前 r 个字符的指纹）
h[r] = s₁·B^r-1 + s₂·B^r-2 + ... + s_l-1·B^r-l+1 + s_l·B^r-l + ... + s_r·B⁰
↑—— 前l-1项（"不要的"） ——↑ ↑—— 我们要的 s[l..r] ——↑

第二步：展开 h[l-1]·B^r-l+1
h[l-1] = s₁·B^l-2 + s₂·B^l-3 + ... + s_l-1·B⁰
乘以 B^r-l+1 后：
h[l-1]·B^r-l+1 = s₁·B^r-1 + s₂·B^r-2 + ... + s_l-1·B^r-l+1
↑—— 恰好等于 h[r] 中"不要的"前l-1项！ ——↑

第三步：两式相减

h[r] − h[l-1] × B^r-l+1 = s_l·B^r-l + s_l+1·B^r-l-1 + ... + s_r = H(s[l..r]) ✓

SVG 图解："前缀相减消去高位"

代码实现

// O(1) 求子串 s[l..r] 的 Hash 值（1-indexed）
unsigned long long getHash(int l, int r) {
    return h[r] - h[l-1] * pw[r-l+1];  // 核心公式！
}
// 判断 s[l1..r1] 和 s[l2..r2] 是否相同：
// getHash(l1, r1) == getHash(l2, r2)  → O(1) 完成！

🔑 核心公式：H(s[l..r]) = h[r] − h[l-1] × B^r-l+1

Hash 值可能非常大（B^n 级别），必须取模控制范围。但怎么取模决定了 Hash 的可靠性。

对比项	方案一：大质数取模	方案二：自然溢出（推荐）
原理	mod = 10⁹+7 或 10⁹+9	用 `unsigned long long`，自动 mod 2⁶⁴
取模方式	每次运算后手动 % mod	不需要手动取模，溢出自动截断
优点	理论安全，冲突率低	代码简洁，速度快，无需处理负数
缺点	需处理负数（+mod）%mod，多次取模慢	可被特殊数据 hack（生日攻击 2³²）
竞赛推荐	被 hack 风险高时（如 CF）	大多数 OI 比赛首选

生日悖论：为什么碰撞不可避免？

生日悖论：在 23 个人中，有两人生日相同的概率 > 50%！

类似地，n 个不同字符串的 Hash 值在 [0, M) 中，任意两个碰撞的概率：

P(碰撞) ≈ n² / (2M)

自然溢出：M = 2⁶⁴ ≈ 1.8×10¹⁹
→ n = 10⁶ 时，P ≈ (10⁶)² / (2×1.8×10¹⁹) ≈ 2.8×10⁻⁸，安全 ✓
→ n = 10⁸ 时，P ≈ 2.8×10⁻⁴，有一定风险 ⚠️
大质数取模：M = 10⁹+7
→ n = 10⁵ 时，P ≈ (10⁵)² / (2×10⁹) ≈ 5×10⁻³，有风险！⚠️

双Hash方案：当碰撞不可容忍

// 双Hash：两组不同的 (B, mod)
const int B1 = 131, B2 = 13331;
const long long mod1 = 1e9+7, mod2 = 1e9+9;
long long h1[N], h2[N], pw1[N], pw2[N];

// 预处理：分别计算两套Hash前缀和
for (int i = 1; i <= len; i++) {
    h1[i] = (h1[i-1] * B1 + s[i]) % mod1;
    h2[i] = (h2[i-1] * B2 + s[i]) % mod2;
    pw1[i] = pw1[i-1] * B1 % mod1;
    pw2[i] = pw2[i-1] * B2 % mod2;
}

// 比较：两组Hash都相同才认为相等
bool isEqual(int l1, int r1, int l2, int r2) {
    return getH1(l1,r1) == getH1(l2,r2)
        && getH2(l1,r1) == getH2(l2,r2);
}

双Hash碰撞概率：≈ 1/(mod1 × mod2) ≈ 10⁻¹⁸

代价：常数×2

💡 经验法则：洛谷/OI 比赛一般单 Hash 够用；CF 等可 hack 平台用双 Hash 更保险。

📋 洛谷 P3370 【模板】字符串哈希
给定 n 个字符串，求其中不同字符串的个数。每个字符串长度 ≤ 1500，n ≤ 10000。

方案一：自然溢出（简洁版）

#include <iostream>
#include <string>
#include <set>
using namespace std;

const int B = 131;
typedef unsigned long long ull;

// 求字符串s的Hash值（自然溢出）
ull getHash(string &s) {
    ull h = 0;
    for (int i = 0; i < s.size(); i++)
        h = h * B + s[i];  // ull溢出自动取模2^64
    return h;
}

int main() {
    int n; cin >> n;
    set<ull> vis;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        vis.insert(getHash(s));  // Hash值去重
    }
    cout << vis.size() << endl;  // 不同Hash值的个数
    return 0;
}

方案二：大质数取模（更安全）

#include <iostream>
#include <string>
#include <set>
using namespace std;

const long long mod = 1e9 + 7;
const int B = 131;

long long getHash(string &s) {
    long long h = 0;
    for (char c : s) h = (h * B + c) % mod;
    return h;
}
// 用法同上，只需改getHash函数

时间复杂度：O(n × |s|)

空间复杂度：O(n)

⚠️ 常见错误：① 用了 signed long long 导致溢出后行为未定义（应该用 unsigned）；② B 取太小的值（如 B=10）导致大量碰撞；③ 忘记本题可以不算前缀和（只需要完整串的 Hash 值即可）。

常见错误清单

❌ 错误1：使用 signed long long 做自然溢出
signed 整数溢出是未定义行为(UB)，编译器可能优化出意想不到的结果。
修正：必须用 unsigned long long。

❌ 错误2：大质数取模忘记处理负数
(h[r] - h[l-1]*pw[len]) % mod 可能为负数！
修正：((h[r] - h[l-1]*pw[len]) % mod + mod) % mod

❌ 错误3：B 取值不当
B 取 2、10 等小值或偶数 → 碰撞率极高。
修正：B 取 131 或 13331（经验值，冲突率低）。

Hash 的应用场景

应用场景	描述	典型题目
字符串去重	判断 n 个字符串中有多少不同	P3370
子串比较	O(1) 判断两个子串是否相同	回文判定、重复子串
二分+Hash	二分答案 + Hash验证 → O(n log n)	最长重复子串
多串匹配	Hash 判断文本中是否包含某模式	简化版字符串匹配
二维Hash	扩展到矩阵子图比较	图片匹配

🔑 Hash 核心总结：进制映射 → 前缀和数组 → O(1)子串查询。记住公式 H(s[l..r]) = h[r] − h[l-1] × B^(r-l+1)，一切迎刃而解！

🎯 最长回文子串问题
给定字符串 S，求其最长回文子串的长度。
回文串：正读和反读相同的字符串，如 "aba"、"abba"、"abcba"、"上海自来水来自海上"。

暴力做法 O(n³)

枚举所有子串 S[i..j]（共 O(n²) 个），逐一判断是否回文（O(n)），总计 O(n³)。

优化：中心扩展法 O(n²)

能不能更快？O(n)！

Manacher 算法（1975）利用已经计算过的回文信息，避免重复扩展。
核心思想：维护"当前最右回文边界 R"，利用镜像关系跳过已知匹配。

暴力 O(n³)：枚举+判断

中心扩展 O(n²)：枚举中心+扩展

Manacher O(n)：镜像加速！

💡 前置知识——回文半径 P[i]：以位置 i 为中心的最大回文范围。
例如 "abacaba"，以 'c' 为中心，左右各扩展 3 个字符，P = 4（含中心）。

📐 回文半径 P[i]：以位置 i 为中心，向左右扩展使得 t[i-k..i+k] 为回文的最大 k+1 值（含中心自身）。
回文长度 = 2 × P[i] − 1（奇数长度回文）

图解：字符串 "abacaba" 逐位置分析

🔑 记忆：P[i] 表示以 i 为中心的最大回文半径（含中心）。回文长度 = 2×P[i]−1。Manacher 的任务就是高效求出所有 P[i]。

⚠️ 问题：上面的讨论只适用于奇数长度回文（有中心字符）。
偶数长度回文（如 "abba"）没有单一中心字符——中心在两个字符之间！怎么办？

解决方案：插入特殊字符 '#'

变换后的美妙性质

变换规则：在每个字符之间及首尾插入 '#' → 新串长度 = 2n+1
关键结论：变换后所有回文都是奇数长度！统一处理！

原串最长回文长度 = max(P[i]) − 1

推导：变换后 P[i] 表示以 i 为中心（含'#'）的回文半径。
去掉所有 '#' 后，实际字符数 = (2×P[i]−1)/2 的整数部分 = P[i]−1

预处理代码

// 将原串s变换为插入'#'的新串t
string t = "#";
for (char c : s) { t += c; t += "#"; }
// s="abba" → t="#a#b#b#a#"
// s="aba"  → t="#a#b#a#"

💡 为什么 '#' 不破坏回文？因为 '#' 在奇数位和偶数位交替出现，镜像对称的 '#' 仍然匹配，原始字符的对称关系不变。

🧠 核心观察：维护变量 C（当前最右回文的中心）和 R（最右边界）。
当 i < R 时，i 在已知回文内部，其关于 C 的镜像 i' = 2C − i 已计算过 P[i']，
可以直接利用 P[i'] 来跳过已知的匹配，避免重复比较！

图解：三种情况

完整核心代码

vector<int> P(t.size(), 1);
int C = 0, R = 0; // C=最右回文中心, R=最右边界

for (int i = 1; i < t.size(); i++) {
    int mirror = 2 * C - i;  // i关于C的镜像位置
    if (i < R) P[i] = min(R - i, P[mirror]); // 情况1/2：利用镜像
    // 尝试向右扩展（跳过已知的部分）
    while (i + P[i] < t.size() && i - P[i] >= 0
           && t[i + P[i]] == t[i - P[i]]) P[i]++;
    // 更新最右边界
    if (i + P[i] > R) { C = i; R = i + P[i]; }
}

时间复杂度：O(n) 线性！

空间复杂度：O(n)

🔑 为什么 O(n)？每次 while 循环匹配成功 → R 右移至少1。R 最多从 0 移到 2n+1，所以扩展总次数 ≤ 2n+1 = O(n)！

目标：用 s = "ababacababc"（长度11，变换后 t 长度 23），追踪每一步 i、t[i]、mirror、P[i]、C、R。
颜色约定： 橙=初始化蓝=越过R,从头扩展绿=镜像加速+扩展红=最大回文

变换后 t（长度 23=2×11+1）：
# a # b # a # b # a # c # a # b # a # b # c #
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
红色为中心 t[11]='c'。整个 t 关于 11 左右对称，暗示中央会有一个超大回文。

📋 逐步状态追踪表（前段：镜像加速区）

i	t[i]	mirror	P[i]初始	P[i]最终	C	R	操作详解
初始	t=全部#交错的 23 长度	—	—	—	0	0	C=0,R=0，P 全部初始化为 1
0	#	—	1	1	0	1	i=0≥R → 跳过镜像；扩展向左越界 → 停；i+P=1>R → C=0,R=1
1	a	—	1	2	1	3	i=1≥R → 从头扩展：t[2]'#'=t[0]'#' ✓→P=2；左越界→停；C=1,R=3
2	#	0	1	1	1	3	i=2<R → mirror=0,P[0]=1→P=1；扩展 t[3]'b'≠t[1]'a' ✗；不更新
3	b	—	1	4	3	7	i=3≥R → 扩展：#'a'✓→b✓→#✓ → P=4；左越界→停；C=3,R=7
4	#	2	1	1	3	7	mirror=2,P[2]=1→P=1；扩展 t[5]'a'≠t[3]'b' ✗；不更新
5	a	—	1	6	5	11	i=5≥R → 扩展：#'a'✓→b✓→#✓→a✓→b?越界→停 → P=6；C=5,R=11
6	#	4	1	1	5	11	mirror=4,P[4]=1→P=1；扩展 t[7]'b'≠t[5]'a' ✗；不更新
7	b	3	1	4	5	11	mirror=3,P[3]=4→但R−i=4→P=min=4；扩展 t[11]'c'≠t[3]'b' ✗；i+P=11≤R 不更新
8	#	2	1	1	5	11	mirror=2,P[2]=1→P=1；扩展 t[9]'a'≠t[7]'b' ✗；不更新
9	a	1	1	2	5	11	mirror=1,P[1]=2→P=2；扩展 t[11]'c'≠t[9]'a' ✗；i+P=11≤R 不更新
10	#	0	1	1	5	11	mirror=0,P[0]=1→P=1；扩展 t[11]'c'≠t[9]'a' ✗；不更新
11	c	—	1	10	11	21	i=11≥R=11 → 从头扩展，连续匹配9层到 P=10！越界→停；C=11,R=21（超大中心诞生）

📋 逐步状态追踪表（后段：R 内镜像复用）

后半段 i=12..22 全部落在 R=21 内，不再越界 + 不做大扩展，直接镜像取值（同色为对称）：

      i=12 mirror=10→P=1 ｜ 13 mirror=9→P=2 ｜ 14 mirror=8→P=1 ｜ 15 mirror=7→P=4 ｜ 16 mirror=6→P=1

      i=17 mirror=5→P=6→但截到R→P=4 ｜ 18 mirror=4→P=1 ｜ 19 mirror=3→P=2→撑到R=21？t[21]='c'≠t[17] ✗→P=2 ｜ 20 mirror=2→P=1 ｜ 21 mirror=1→P=2 ｜ 22 mirror=0→P=1

完整 P 数组：[1,2,1,4,1,6,1,4,1,2,1,10,1,2,1,4,1,4,1,2,1,2,1]
max(P)=10，答案 = max(P)−1 = 9（即 "babacabab"）

💡 为什么后半段几乎不花时间？因为 t 关于中心 11 左右对称，R 直接推进到 21。i=12..22 每步要么 mirror 取值即终值、要么截断到 R（17 举例），只有一次扩展就停。这就是 O(n) 的关键：R 每轮最多右移一步，总共只移动 ≈ n 次；而"从头逐字符比较"的大扩展全被镜像省掉。

📋 洛谷 P3805 【模板】Manacher算法
给定一个长度为 n 的字符串，求其最长回文子串的长度。n ≤ 1.1×10⁷。

完整代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int manacher(string &s) {
    // 第一步：插入'#'，统一奇偶回文
    string t = "#";
    for (char c : s) { t += c; t += "#"; }
    // s="abba" → t="#a#b#b#a#" (长度9=2×4+1)
    
    vector<int> P(t.size(), 1);
    int C = 0, R = 0;   // C=最右回文中心, R=最右边界
    int ans = 0;
    
    for (int i = 0; i < t.size(); i++) {
        // 核心：利用镜像加速
        if (i < R) P[i] = min(R - i, P[2*C - i]);
        // 尝试扩展（可能一步都不走）
        while (i - P[i] >= 0 && i + P[i] < t.size()
               && t[i-P[i]] == t[i+P[i]]) P[i]++;
        // 更新最右边界
        if (i + P[i] > R) { C = i; R = i + P[i]; }
        // 原串回文长度 = P[i] - 1
        ans = max(ans, P[i] - 1);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);  // 大数据量必须加速读入！
    string s; cin >> s;
    cout << manacher(s) << endl;
    return 0;
}

时间复杂度：O(n)

空间复杂度：O(n)

SVG 模拟：s = "aba" 的执行过程

⚠️ 常见错误：① n 很大时必须 ios::sync_with_stdio(0)；② 忘记 P[i]-1 才是原串回文长度；③ t 的长度是 2n+1，数组要开够。

🎯 为什么需要备份？
Manacher 是 O(n) 线性最优，但细节多（插'#'、镜像加速、P[i] 越界）极易写错。考场上两难的题，先写又短又稳的 Hash+二分拿 100 分，再想优化。它只做一件事——O(1) 判断"某一段子串是不是回文"。
总复杂度 O(n log n)：对每个中心二分半径（log n 次判回文），共 n 个中心。

一、先读懂"哈希怎么判回文"——用具体例子走一遍

① 两个前缀哈希表。
对串 s 做正向前缀哈希，再把 s 反转成 rev，对 rev 做另一套前缀哈希。
② O(1) 取任意子串哈希：
hash(s, l, r) = h[r+1] − h[l] × B^r−l+1　（h 下标从 1 起，h[0]=0）
③ 判断回文：

s[l..r] 是回文 ⟺ hash(s, l, r) == hash(rev, n-1-r, n-1-l)

左边=正向哈希；右边=在反转串里取一段，两者数值相等即回文。

🖨️ 为什么右边区间是 [n-1-r, n-1-l]，不是 [l,r]？
关键想通一句：“s[l..r] 正着读”，等于“把整串反转后，那一小段仍是从左往右读”。
验证：设 s="abcb"（n=4），ls=0, r=1，即子串 "ab"。反转 rev="bcba"。
· 若直接取 rev[0..1] = "bc" → 错，不是 "ab" 的反转！
· 正确：n−1−r=3−1... 按下标换算：l_rev=n−1−r=4−1−1=2，r_rev=n−1−l=4−1−0=3 → rev[2..3]="ba" = "ab" 的反转 ✓
所以"取反串中的镜像区间"才能让 正向子串与反向子串逐字符方向一致，从而用相等判断回文。

⚠️ 最容易写错点：这个镜像区间 [n−1−r, n−1−l] 的 l、r 顺序是反的（右端用 l、左端用 r）。照抄 [l,r] 会得到错误的反向哈希，整题全错。建议先写出具体下标验一次再上机。

二、为什么能二分？——回文性的"单调"

固定一个回文中心，比如"以字符 i 为中心，能包住半径 x 的对称段"。
关键性质：若半径 x 的两端对称成立（回文），那么任意更小的半径（更短的对称段）必然也成立。
→ 于是"半径 x 是否回文"随 x 增大，从 True 只变到 False 一次，形成单调二分边界：

✓ ✓ ✓ ✓ | ✗ ✗ ✗　（左侧可行、右侧不可行，二分找最大可行半径）

判一次回文 O(1)，二分 O(log n) → 每个中心 O(log n)。

三、奇偶两种中心要分开

类型	中心	判回文区间	真实长度
奇数长度	单字符 i（如 "aba" 以 b 为中心）	[i−m, i+m]	2m+1
偶数长度	两字符 i、i+1 之间（如 "abba"）	[i−m+1, i+m]	2m

💡 奇数中心用 odd(i)：以 i 为轴往外扩 m；偶数中心用 even(i)：轴在 i 与 i+1 之间。
对每个中心二分出最大可行 m，两端长度取 max，即为答案。两端 O(1) 判回文全靠第一步的哈希表。

总复杂度：O(n log n)

判一次回文：O(1)

📋 洛谷 P3805：求最长回文子串长度，n ≤ 1.1×10⁷。
用 Hash+二分 可过普通数据；正式/大样例请切回 Manacher。
注：本段中 `ok(l,r)` 用双哈希判定，把碰撞概率压到接近 0。

代码如何跟思路对应

代码里 h 建正向前缀哈希、rh 建 反转串 rs 的前缀哈希、pw 存 B 的幂。
sub(H,l,r) → 取 H 数组中的子串哈希 H[r+1]−H[l]·pw[r−l+1]。
isPal(l,r)：正向取 sub(h,l,r)，反向取 sub(rh, n−1−r, n−1−l)（镜像区间，方向与正向对齐），相等即回文。
odd(i) 以 i 为轴二分半径、even(i) 以 i,i+1 之间为轴二分——对应思路页"奇偶两种中心"。

完整代码（unsigned long long 自然溢出 + 反向Hash）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int B = 131;

int n; string s, rs;
vector<ull> h, rh, pw;

// 子串哈希: hash of s[l..r] (l,r 为原串下标)
ull sub(vector<ull>&H, int l, int r) {
    return H[r+1] - H[l]*pw[r-l+1];
}

// 判 s[l..r] 是否为回文: 正向Hash == 反向Hash(区间镜像翻转)
bool isPal(int l, int r) {
    ull f = sub(h, l, r);
    ull b = sub(rh, n-1-r, n-1-l);
    return f == b;
}

// 奇数长度: 以 i 为中心二分半径
int odd(int i) {
    int lo=0, hi=min(i, n-1-i);
    while(lo<hi){ int m=(lo+hi+1)/2;
        isPal(i-m, i+m)?lo=m:hi=m-1; }
    return 2*lo+1;
}

// 偶数长度: 以 i, i+1 之间为中心二分长度的一半
int even(int i) {
    int lo=0, hi=min(i+1, n-1-i);
    while(lo<hi){ int m=(lo+hi+1)/2;
        isPal(i-m+1, i+m)?lo=m:hi=m-1; }
    return 2*lo;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> s; n = s.size();
    rs = s; reverse(rs.begin(), rs.end());

    // 正向 & 反向前缀Hash (下标从1起，H[0]=0)
    h.assign(n+1, 0); rh.assign(n+1, 0); pw.assign(n+1, 1);
    for(int i=1; i<=n; i++){
        pw[i]=pw[i-1]*B;
        h[i]=h[i-1]*B+(ull)s[i-1];
        rh[i]=rh[i-1]*B+(ull)rs[i-1];
    }

    int ans=1;
    for(int i=0; i<n; i++){
        ans=max(ans, odd(i));
        if(i+1<n) ans=max(ans, even(i));
    }
    cout << ans << endl;
    return 0;
}

Manacher vs Hash+二分对照

维度	Manacher	Hash + 二分（备份）
时间复杂度	O(n) 线性	O(n log n)
实现难度	较难（镜像加速易错）	简单（只判回文）
正确性风险	无哈希碰撞	哈希碰撞（用双哈希压到近0）
适用	模板题 / 超大 n	普通数据 / 临场快速兜底

🔑 结论：考场上优先写 Manacher；万一没把握，先用 Hash+二分拿到 100 分的稳妥分，再优化。这就是它作为备份解法的价值。

🎯 字符串匹配问题
给定文本串 T（长度 n）和模式串 P（长度 m），在 T 中找出所有 P 出现的位置（起始下标）。
例如 T="ababcabab"，P="aba"，P 在位置 0、2、5 出现。

暴力匹配 O(n×m) 演示

方案	暴力匹配	KMP	优化点
失配后	i回退，j归零	i不回退，j=next[j]	利用已匹配信息
时间复杂度	O(n × m)	O(n + m)	线性！

💡 KMP 的精髄：文本串指针 i 永远不回退！失配时只回退模式串指针 j，而且跳到 next[j-1] 而不是 0。

📐 前后缀定义
对于字符串 s[0..k]：
前缀：以 s[0] 开头的子串（如 s[0..0], s[0..1], ...）
后缀：以 s[k] 结尾的子串（如 s[k..k], s[k-1..k], ...）
最长公共前后缀：最长的既是前缀又是后缀的子串（不能是整串本身）

📐 next[i] 的定义：
next[i] = 模式串 P[0..i] 的最长相等前后缀的长度。
即 P[0..next[i]-1] = P[i-next[i]+1..i]，且 next[i] < i+1

逐步计算：P = "ababcabab"（9个字符）

🔑 next[i] 的本质：P[0..i] 中，最长相等前后缀的长度。它告诉我们：失配后，j 可以跳到 next[j-1] 继续，因为前缀已经匹配过了！

📐 计算 next[] 的思路：用两个指针 i 和 j，i 遍历模式串（从1开始），j 表示当前匹配的前缀长度。
如果 P[i] == P[j]，则 j++，next[i] = j；否则 j = next[j-1] 回退，直到 j=0 或匹配。

SVG 图解：P = "ababcabab" 的 next[] 计算

🔑 核心逻辑：P[i] ≠ P[j] 时，不是回退到 0，而是 j = next[j-1]，因为 P[0..j-1] 已经是 P[0..i-1] 的最长公共前后缀，回退到 next[j-1] 可以复用更多已匹配信息！

📐 KMP 匹配规则：
遍历文本串 T，用指针 i 指向 T[i]，j 指向 P[j]。
① T[i] == P[j]：j++，继续比较下一个
② T[i] ≠ P[j]：j = next[j-1]（回退模式串指针，i 不动！）
③ j == m：匹配成功！记录位置 i-m+1，然后 j = next[j-1]

SVG 图解：T="ababcabab"，P="abab"

🔑 KMP 的核心：文本指针 i 永远不回退！模式串指针 j 在失配时跳到 next[j-1]，利用了"已匹配部分的前后缀重叠"这一宝贵信息。

📋 洛谷 P3375 【模板】KMP
给定文本串 T 和模式串 P，求 P 在 T 中所有出现位置（1-based），并输出 next 数组。

完整代码（含逐行注释）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string T, P;
    cin >> T >> P;
    int n = T.size(), m = P.size();
    
    // ========== 第一步：计算 next 数组 ==========
    vector<int> nxt(m, 0);  // next数组，初始化为0
    for (int i = 1, j = 0; i < m; i++) {
        // 失配时回退j：不是j=0，而是j=next[j-1]
        while (j > 0 && P[i] != P[j]) j = nxt[j-1];
        // 匹配成功：前缀长度+1
        if (P[i] == P[j]) j++;
        // 记录当前位置的next值
        nxt[i] = j;
    }
    
    // ========== 第二步：KMP 匹配 ==========
    for (int i = 0, j = 0; i < n; i++) {
        // 失配时回退j（和上面完全一样的逻辑！）
        while (j > 0 && T[i] != P[j]) j = nxt[j-1];
        // 匹配成功
        if (T[i] == P[j]) j++;
        // 完全匹配：记录位置
        if (j == m) {
            cout << i - m + 2 << endl; // 1-based起始位置
            j = nxt[j-1]; // 继续搜索下一个匹配
        }
    }
    
    // 输出 next 数组
    for (int i = 0; i < m; i++) cout << nxt[i] << " ";
    cout << endl;
    return 0;
}

预处理 next[]：O(m)

匹配过程：O(n)

总时间复杂度：O(n + m)

空间复杂度：O(m)

复杂度证明

为什么匹配过程是 O(n)？
定义势能函数 Φ = j（模式串指针的位置）。
每次 i++ 时：Φ 最多增加 1（j++ 最多一次）
每次 while 回退时：Φ 减少（j = next[j-1] < j）
总势能变化 ≤ n（增加不超过 n 次），而 Φ ≥ 0，
所以 while 回退的总次数 ≤ n。

∴ 总操作数 = n(前进) + ≤n(回退) = O(n)

常见错误清单

❌ 错误1：失配时 j = 0（归零）
这样就退化为暴力匹配！必须 j = next[j-1]，利用已匹配的前后缀信息。

❌ 错误2：计算 next 和匹配时逻辑不一致
计算 next[] 时是 P[i] 与 P[j] 比较；匹配时是 T[i] 与 P[j] 比较。
两者的回退逻辑 while(j>0 && ...!=P[j]) j=nxt[j-1] 完全相同！

❌ 错误3：匹配成功后忘记 j = next[j-1]
找到一次匹配后，如果不回退 j，会跳过后续可能的匹配。
修正：if (j == m) { pos.push_back(...); j = nxt[j-1]; }

❌ 错误4：next 数组定义混淆
有些教材的 next[0]=-1 或整体偏移1。本教程用 next[i]=P[0..i]最长公共前后缀长度，next[0]=0。

KMP vs Hash 应用对比

对比项	KMP	字符串 Hash
适用场景	精确找模式串所有出现位置	快速判断两个子串是否相同
时间复杂度	O(n + m)	O(n)预处理 + O(1)查询
空间复杂度	O(m)	O(n)
优点	精确、无碰撞风险	灵活，支持任意子串比较
缺点	只能匹配一个模式	有碰撞风险（双Hash可解）
典型题目	P3375 模式匹配	P3370 字符串去重

🔑 KMP 核心总结：next[i] = P[0..i] 最长公共前后缀长度。失配时 j = next[j-1]，文本指针 i 永远不回退。理解"前后缀重叠"就理解了 KMP！

📐 Trie（字典树/前缀树）：一棵多叉树，每条边代表一个字符。从根到某个节点的路径表示一个字符串前缀。
核心操作：插入字符串 O(|s|)、查询字符串是否存在 O(|s|)、查询前缀 O(|s|)。

逐步构建：插入 "abc", "ab", "abd", "bcd"

🔑 Trie 的本质：把字符串集合变成一棵树，公共前缀共享同一条路径。每个节点最多有 Σ 个孩子（Σ=字符集大小）。

📋 洛谷 P2580 名字的正确拼写
给定 n 个正确名字，再给 m 个点名查询，判断每个查询：
OK（首次查到）/ REPEAT（重复查到）/ WRONG（不在名单中）

完整代码

#include <iostream>
#include <string>
using namespace std;

const int MAXN = 500005;
int ch[MAXN][26], cnt = 0; // ch[u][c]=节点u的第c个孩子
bool ed[MAXN];  // 结尾标记：是否为某个名字的最后字符
bool vis[MAXN]; // 访问标记：是否已被点名过

// 插入名字s到Trie
void insert(string s) {
    int u = 0;  // 从根节点出发
    for (char c : s) {
        int v = c - 'a';  // 字符映射到0~25
        if (!ch[u][v]) ch[u][v] = ++cnt; // 无此孩子则新建
        u = ch[u][v];  // 走向孩子
    }
    ed[u] = true;  // 标记：这是一个名字的结尾
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        insert(s);  // 构建Trie
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        string s; cin >> s;
        int u = 0; bool ok = true;
        for (char c : s) {
            int v = c - 'a';
            if (!ch[u][v]) { ok = false; break; } // 路径不存在
            u = ch[u][v];
        }
        if (!ok) cout << "WRONG" << endl;       // 不在名单中
        else if (vis[u]) cout << "REPEAT" << endl; // 已点过名
        else { vis[u] = true; cout << "OK" << endl; } // 首次点名
    }
    return 0;
}

建树时间：O(∑|s|)

每次查询：O(|s|)

空间复杂度：O(∑|s| × 26)

SVG：查询 "Repeat" 的过程

⚠️ 常见错误：① 忘记 ed[] 标记——走到最后不检查是否为结尾（"ab"的前缀"a"不是完整名字）；② vis[] 数组要开到 MAXN（节点数可能很多）；③ 字符集不是小写字母时要调整映射方式。

常见错误清单

❌ 错误1：空间开太大或太小
数组大小 = 所有字符串总长度 + 1。如 ∑|s| ≤ 500000，则 MAXN = 500005。
ch[MAXN][26] 占 500005×26×4 字节 ≈ 50MB，注意内存限制！

❌ 错误2：忘记结尾标记 ed[]
查询时只检查路径存在 ≠ 字符串存在。必须检查最后一个节点的 ed[] 标记。

❌ 错误3：字符集映射错误
大写字母：c-'A'；数字：c-'0'；包含大小写：需要26+26=52个孩子。

Trie 的应用场景

应用场景	描述	典型题目
字符串存在性查询	判断一个字符串是否在集合中	P2580 名字拼写
前缀查询	统计以某前缀开头的字符串个数	自动补全
最大异或对	将数字转为二进制串，Trie上贪心	最大XOR
AC自动机基础	Trie + KMP fail → 多模式匹配	Day03 预告
01Trie	处理二进制/位运算问题	区间异或最值

四大算法综合对比

算法	解决的问题	时间复杂度	核心思想
Hash	快速比较子串	O(n)预处理+O(1)查询	进制映射→指纹
Manacher	最长回文子串	O(n)	镜像加速
KMP	模式匹配	O(n+m)	next数组避免回退
Trie	字符串集合查询	O(\|s\|)每次	前缀树共享路径

🔑 Trie 核心总结：边代表字符，路径代表字符串。公共前缀共享节点。插入和查询都是 O(|s|)。记住 ch[][] 二维数组的存储方式！

编号	题目	知识点	难度
1	P1210 [USACO1.3] 最长的回文 Calf Flac	Manacher 入门	普及
2	P9606 [CERC2019] ABB	最长回文后缀（KMP/Manacher）	普及+/提高−
3	P1872 回文串计数	Hash + DP	普及+/提高−
4	P4391 [BOI2009] Radio Transmission 无线传输	KMP 循环节	普及+/提高−
5	P11276 第一首歌	KMP border	普及+/提高−
6	P10470 前缀统计	Trie	普及+/提高−
7	P15835 [蓝桥杯第一届国际赛] 基因配对	KMP	普及+/提高−
8	P1659 [国家集训队] 拉拉队排练	Manacher + 快速幂	提高
9	P2353 背单词	KMP + 区间查询	提高
10	P8085 [COCI 2011/2012 #4] KRIPTOGRAM	Hash + KMP	提高

参考答案思路

1. P1210：Manacher 入门，忽略非字母字符后求最长回文子串，注意原串还原
2. P9606：求最长回文后缀，可用 Manacher 或 KMP（将反串与原串拼接求 nxt）
3. P1872：Hash 统计不同回文子串数量，结合 DP 或枚举中心扩展
4. P4391：KMP 求最短循环节：答案 = n - nxt[n]
5. P11276：KMP 的 border（前缀函数）应用，利用 nxt 数组递推求解
6. P10470：Trie 模板，在 Trie 节点上维护 cnt 统计以某串为前缀的个数
7. P15835：KMP 应用，利用 nxt 数组处理基因序列配对问题
8. P1659：Manacher 求出所有回文半径，按奇偶分类 + 前缀和 + 快速幂统计方案数
9. P2353：KMP 求每个串的周期，结合树状数组/线段树做区间查询
10. P8085：字符串 Hash 确定匹配位置，再用 KMP 验证，注意双 Hash 防碰撞

💡 做题建议：先做入门题（1-3）感受各算法基本用法，再做中等题（4-7）掌握 KMP/Manacher 的变形应用，最后挑战提高题（8-10）。注意 KMP 的 nxt 数组和 Manacher 的 P 数组是核心，务必理解透彻！

📖

Day 02 完成！

字符串四大算法：Hash · 马拉车 · KMP · Trie

📌 字符串 Hash：进制映射 → 前缀和 → O(1) 子串查询
📌 Manacher：插入'#' 统一奇偶 → 镜像加速 → O(n) 线性
📌 KMP：next 数组 = 最长公共前后缀 → j=next[j-1] → O(n+m)
📌 Trie：前缀树 → 边是字符路径是串 → O(|s|) 查询

🎯 明日预告：Day 03 · 图论基础
最短路算法（Dijkstra / Floyd） · 最小生成树 · 拓扑排序

✏️ 🧹

#️⃣ 字符串 Hash · 问题引入

#️⃣ Hash · 进制映射数学推导

#️⃣ Hash 前缀和 · 字符串的"指纹数组"

#️⃣ 从 Hash 前缀和取出任意子串

#️⃣ Hash 的灵魂 · 模数怎么选？

#️⃣ Hash · 例题 P3370 完整代码

#️⃣ Hash · 常见错误 & 应用总结

🔄 Manacher · 问题引入

🔄 回文半径 P[i] 详解（图解）

🔄 Manacher · 奇偶回文统一处理

🔄 Manacher · 镜像加速（核心 O(n) 优化）

🔄 Manacher 逐步模拟 — 以 "ababacababc" 为例

🔄 Manacher · 例题 P3805 完整代码

🔄 备份方案：Hash + 二分求最长回文（思路)

🔄 Hash + 二分 · 完整代码（P3805 备份解）

🔍 KMP · 问题引入与暴力匹配演示

🔍 KMP · next 数组的定义与逐步计算

🔍 KMP · next 数组计算过程（指针图解）

🔍 KMP · 匹配过程详解（滑动图解）

🔍 KMP · 例题 P3375 完整代码

🔍 KMP · 常见错误与应用对比

🌲 字典树 Trie · 结构与逐步构建

🌲 Trie · 例题 P2580 完整代码

🌲 Trie · 常见错误与应用扩展

📝 下午练习题单