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 = "aba"（变换后 t = "#a#b#a#"，长度7），从零开始追踪算法每一步中 i、t[i]、mirror、P[i]、C、R 的变化。
颜色约定： 橙=初始化蓝=正常步骤绿=镜像+扩展红=关键步骤灰=完成

变换后数组： t = [ # a # b # a # ]
idx: 0 1 2 3 4 5 6

📋 逐步状态追踪表

步骤	i	t[i]	mirror	P[i] 初始	P[i] 最终	C	R	操作详解
初始	—	t = " # a # b # a # "		—	—	0	0	C=0, R=0，P 数组全部初始化为 1
①	0	#	—	1	1	0	1	i=0 ≥ R=0 → 跳过镜像；扩展：t[1]='a' vs t[-1]越界 → 停；i+P=1 > R → C=0, R=1
②	1	a	—	1	2	1	3	i=1 ≥ R=1 → 跳过镜像；扩展：t[2]='#'=t[0]='#' ✓ → P=2；t[3]='b' vs t[-1]越界 → 停；i+P=3 > R=1 → C=1, R=3
③	2	#	0	1	1	1	3	i=2 < R=3 → mirror=2×1−2=0，P[0]=1 → P[2]=min(1,1)=1；扩展：t[3]='b' vs t[1]='a' → ✗ 不匹配，停；i+P=3 ≤ R=3 → 不更新C,R
④	3	b	—	1	4	3	7	i=3 ≥ R=3 → 跳过镜像；扩展：t[4]='#'=t[2]='#' ✓ → P=2；t[5]='a'=t[1]='a' ✓ → P=3；t[6]='#'=t[0]='#' ✓ → P=4；t[7]越界 → 停；i+P=7 > R=3 → C=3, R=7
⑤	4	#	2	1	1	3	7	i=4 < R=7 → mirror=2×3−4=2，P[2]=1 → P[4]=min(1,3)=1；扩展：t[5]='a' vs t[3]='b' → ✗ 不匹配，停；i+P=5 ≤ R=7 → 不更新
⑥	5	a	1	2	2	3	7	i=5 < R=7 → mirror=1，P[1]=2 → P[5]=min(2,2)=2；扩展：t[7]越界 → 停；i+P=7 ≤ R → 不更新
⑦	6	#	0	1	1	3	7	i=6 < R=7 → mirror=0，P[0]=1 → P[6]=min(1,1)=1；扩展：t[7]越界 → 停；i+P=7 ≤ R → 不更新
最终 P = [1, 2, 1, 4, 1, 2, 1]，max(P) = 4，答案 = max(P) − 1 = 3（即 "aba"）

🔍 关键步骤图解

💡 关键观察：步骤③中 mirror=0 给出的初始值 P[2]=1，扩展第一层就失败了（t[3]='b' ≠ t[1]='a'），这就是镜像加速的体现——即使只比较一次就停，也比从头扩展快。步骤④是核心：i=3 时 i≥R，必须从头扩展，但连续3次匹配把 P 推到4，一举覆盖了整个字符串！

对称性验证：最终 P = [1, 2, 1, 4, 1, 2, 1] 关于中心 i=3 完美对称！这是因为 "#a#b#a#" 本身就是以位置3为中心的完整回文。

📋 洛谷 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，数组要开够。

🎯 字符串匹配问题
给定文本串 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 逐步模拟 — 以 "aba" 为例

🔄 Manacher · 例题 P3805 完整代码

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

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

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

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

🔍 KMP · 例题 P3375 完整代码

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

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

🌲 Trie · 例题 P2580 完整代码

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

📝 下午练习题单