字符串

先建立认知：

字符串哈希 = 把一个字符串映射成一个数字（哈希值），通过比较数字来快速比较字符串。
核心价值：把"比较两个字符串是否相等"从 O(长度) 降到 O(1)——直接比哈希值。这让很多字符串问题变得简单。

一、为什么需要字符串哈希

直接比较两个字符串是否相等要逐字符比，O(长度)。如果要频繁比较子串（比如判断很多对子串是否相等），每次 O(长度) 就太慢。

哈希的思路：给每个字符串算一个数字（哈希值）。如果两个字符串相等，它们的哈希值一定相等；如果哈希值不同，字符串一定不同。 这样比较字符串就变成比较数字，O(1)。

这和 1.1 学的"用 map 计数""用数字代替复杂对象"是一脉相承的思想——把复杂的东西映射成简单的数字来处理。

二、字符串哈希的核心：多项式哈希

基本思想

把字符串看成一个 P 进制的数。每个字符对应一个数字（如 a→1, b→2），整个字符串的哈希值就是这些数字按 P 进制组合：

hash(s) = s[0]×P^(n-1) + s[1]×P^(n-2) + ... + s[n-1]×P^0

其中 P 是一个基数（通常取一个质数，如 131 或 13331）。为了防止哈希值过大溢出，对一个大数取模（或者利用 unsigned long long 自然溢出）。

实现：前缀哈希（关键技巧）

为了能 O(1) 求任意子串的哈希值，预处理前缀哈希数组（类似前缀和，接 1.3）：

typedef unsigned long long ull;
const int N = 1e5 + 5;
const ull P = 131;        // 基数（经验值，131 或 13331）

ull h[N];                 // h[i] = 前 i 个字符的哈希值
ull p[N];                 // p[i] = P 的 i 次方（预处理，用于求子串哈希）

void initHash(string s) {
    int n = s.size();
    p[0] = 1;
    h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + s[i-1];   // 前缀哈希递推（类似前缀和）
        p[i] = p[i-1] * P;             // P 的幂
    }
}

// O(1) 求子串 s[l..r] 的哈希值（下标从1开始）
ull getHash(int l, int r) {
    return h[r] - h[l-1] * p[r - l + 1];
}

理解 getHash（核心公式）：

• h[r] 是前 r 个字符的哈希，h[l-1] 是前 l-1 个字符的哈希。
• 要得到 s[l..r] 的哈希，需要把 h[l-1] 的"位权"对齐后减掉——h[l-1] * p[r-l+1] 就是把前 l-1 部分左移到正确位置，相减就剩下 s[l..r]。
• 这和前缀和的 s[r]-s[l-1] 思想一样，只是因为是 P 进制，要乘上位权 p[r-l+1]。

用 unsigned long long 自然溢出（不手动取模）是个常用技巧——ull 溢出相当于自动对 2⁶⁴ 取模，省去取模操作，代码更简洁。基数 P 取 131 或 13331 这些经验值。

三、字符串哈希的典型应用

应用 1：判断两个子串是否相等（O(1)）

// 判断 s[a..b] 和 s[c..d] 是否相等
bool equal(int a, int b, int c, int d) {
    if (b - a != d - c) return false;        // 长度不同，肯定不等
    return getHash(a, b) == getHash(c, d);   // 哈希相同则相等
}

这是哈希最核心的用途——O(1) 比较任意两个子串。

应用 2：找字符串中的重复子串、回文判断等

• 判断回文：把字符串和它的反转串都算哈希，比较对应子串的正、反哈希是否相等。
• 找最长重复子串：结合二分答案（接 1.2）——二分子串长度，用哈希检查是否存在两个相同的该长度子串。
• 字符串匹配：在文本里找模式串，用哈希逐位比较（虽然 KMP 更专业，但哈希也能做）。

应用 3：判断多个字符串是否有相同的

把每个字符串的哈希值存进 set 或 map，相同哈希值的就是相同字符串（O(1) 查重）。

四、哈希冲突问题（要知道）

哈希冲突：不同的字符串可能算出相同的哈希值（因为把无限多字符串映射到有限的数字）。虽然概率很小，但存在。

降低冲突的方法：

• 选好的基数和模数（P=131/13331，模数用大质数，或用 ull 自然溢出）。
• 双哈希（更保险）：用两组不同的 (P, MOD) 算两个哈希值，两个都相同才认为字符串相等。冲突概率极低。

铜牌阶段，单哈希（ull 自然溢出）通常够用。如果担心被卡（有些题会故意构造冲突数据），用双哈希。知道有冲突这回事，遇到哈希题 WA 且逻辑没错时，考虑是不是冲突了。

五、字符串哈希解题思维

1. 识别：需要频繁比较子串是否相等、找重复子串、回文判断等 → 考虑哈希。
2. 预处理：算前缀哈希 h[] 和幂数组 p[]。
3. O(1) 查询：用 getHash(l, r) 求任意子串哈希。
4. 比较：通过比哈希值判断子串相等。
5. 注意冲突：必要时用双哈希。

六、本节速记卡

• 字符串哈希：把字符串映射成数字，O(1) 比较两个字符串/子串是否相等。
• 多项式哈希：把字符串看成 P 进制数，hash = Σ s[i]×P^(...)。
• 前缀哈希（核心）：预处理 h[i]=h[i-1]×P+s[i-1]、p[i]=p[i-1]×P。
• 子串哈希（O(1)）：getHash(l,r) = h[r] - h[l-1]×p[r-l+1]（类似前缀和+位权）。
• 技巧：用 unsigned long long 自然溢出（免取模），P 取 131/13331。
• 应用：比较子串、找重复子串（配二分）、回文判断、字符串查重。
• 冲突：单哈希通常够，担心被卡用双哈希。

字符串哈希是处理字符串问题的"瑞士军刀"——思想简单（映射成数字）、应用广泛（任何需要比较子串的地方）。核心是前缀哈希 + O(1) 求子串哈希这个技巧，和前缀和一脉相承。把模板记住，很多字符串题都能用哈希暴力解决。

它的最大优点是通用且好写——不像 KMP 那样有固定套路要记，哈希更灵活，配合二分能解决很多"最长重复子串"之类的问题。

下一节 6.2 KMP——经典的字符串匹配算法，专门解决"在文本串里找模式串出现的位置"，O(n+m) 高效。它有固定的模板（next 数组），是字符串的经典必学内容，但比哈希稍难理解一点。

配套练习题

好，给你 5 道字符串哈希题，子串比较、查重、回文判断、重复子串（配二分）。哈希的核心是"前缀哈希 + O(1) 求子串哈希"，把这个模板练熟很实用。

老规矩：先自己写，重点想清楚"哪里需要比较子串、怎么用哈希O(1)实现",再展开对照。

第 1 题：子串比较（哈希模板 —— 必会）

题意：给一个字符串 s 和 q 次询问，每次给四个数 a b c d，问子串 s[a..b] 和 s[c..d] 是否相等（下标从1开始）。相等输出 YES，否则 NO。

输入样例
abcabc
3
1 3 4 6
1 2 4 5
1 3 2 4

输出样例
YES
YES
NO

（s[1..3]="abc", s[4..6]="abc" 相等；s[1..2]="ab", s[4..5]="ab" 相等；s[1..3]="abc", s[2..4]="bca" 不等）

考点：字符串哈希模板。预处理前缀哈希 h[] 和幂 p[]，用 getHash(l,r) O(1) 比较。这是哈希的核心模板。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const ull P = 131;
ull h[N], p[N];

void initHash(string s) {
    int n = s.size();
    p[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
}

ull getHash(int l, int r) {
    return h[r] - h[l-1] * p[r - l + 1];
}

int main() {
    string s;
    cin >> s;
    initHash(s);
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (b - a != d - c) { cout << "NO\n"; continue; }  // 长度不同
        cout << (getHash(a, b) == getHash(c, d) ? "YES" : "NO") << "\n";
    }
    return 0;
}

第 2 题：统计不同子串个数（哈希查重 —— 应用）

题意：给一个字符串 s，统计它有多少个不同的长度为 k 的子串。

输入样例
ababab
2

输出样例
2

（长度2的子串有 "ab","ba","ab","ba","ab"，不同的只有 "ab" 和 "ba"，共2个）

考点：用哈希给每个长度为k的子串算哈希值，存进 set 去重，set 大小就是不同子串数。练习"哈希值存set查重"。

提示：① 预处理哈希；② 枚举每个起点，求长度为k的子串哈希 getHash(i, i+k-1)，插入 set；③ set 的大小就是答案。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const ull P = 131;
ull h[N], p[N];

void initHash(string s) {
    int n = s.size();
    p[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
}
ull getHash(int l, int r) { return h[r] - h[l-1] * p[r - l + 1]; }

int main() {
    string s;
    int k;
    cin >> s >> k;
    initHash(s);
    int n = s.size();
    set<ull> st;
    for (int i = 1; i + k - 1 <= n; i++)    // 枚举每个长度k的子串起点
        st.insert(getHash(i, i + k - 1));    // 哈希存set去重
    cout << st.size() << "\n";
    return 0;
}

第 3 题：回文判断（哈希应用 —— 正反哈希）

题意：给一个字符串 s 和 q 次询问，每次问子串 s[l..r] 是否是回文串。是输出 YES，否则 NO。

输入样例
abacaba
3
1 7
1 3
2 4

输出样例
YES
YES
NO

（s[1..7]="abacaba"是回文；s[1..3]="aba"是回文；s[2..4]="bac"不是）

考点：回文判断——一个子串是回文 ⟺ 它正着读和反着读相等。对原串和反转串分别求哈希，比较子串的正哈希和反哈希。练习"正反哈希判回文"。

提示：① 对 s 求前缀哈希（正向）；② 对 reverse(s) 求前缀哈希（反向）；③ 子串 s[l..r] 是回文 ⟺ 它在正串的哈希 == 它在反串对应位置的哈希。注意反串的下标对应关系（s[l..r] 在反串中是 [n-r+1..n-l+1]）。这题下标对应有点绕，仔细处理。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const ull P = 131;
ull h1[N], h2[N], p[N];   // h1正向，h2反向

int main() {
    string s;
    cin >> s;
    int n = s.size();
    string r = s;
    reverse(r.begin(), r.end());

    p[0] = 1; h1[0] = 0; h2[0] = 0;
    for (int i = 1; i <= n; i++) {
        h1[i] = h1[i-1] * P + s[i-1];    // 正向哈希
        h2[i] = h2[i-1] * P + r[i-1];    // 反向哈希
        p[i] = p[i-1] * P;
    }
    auto getH1 = [&](int l, int r) { return h1[r] - h1[l-1] * p[r-l+1]; };
    auto getH2 = [&](int l, int r) { return h2[r] - h2[l-1] * p[r-l+1]; };

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // s[l..r] 在反串中对应 [n-r+1 .. n-l+1]
        ull forward = getH1(l, r);
        ull backward = getH2(n - r + 1, n - l + 1);
        cout << (forward == backward ? "YES" : "NO") << "\n";
    }
    return 0;
}

第 4 题：查找模式串出现次数（哈希匹配 —— 字符串匹配）

题意：给一个文本串 text 和一个模式串 pattern，求 pattern 在 text 中出现了多少次（可重叠）。

输入样例
ababab
ab

输出样例
3

（"ab" 在 "ababab" 中出现3次：位置0,2,4）

考点：用哈希做字符串匹配。先算 pattern 的哈希，然后在 text 中枚举每个长度为 |pattern| 的子串，比较哈希。练习"哈希实现字符串匹配"（KMP的替代方案）。

提示：① 对 text 预处理前缀哈希；② 算 pattern 的哈希值；③ 枚举 text 中每个起点 i，求 getHash(i, i+m-1)（m=pattern长度），和 pattern 哈希比较，相等则计数。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e6 + 5;
const ull P = 131;
ull h[N], p[N];

void initHash(string s) {
    int n = s.size();
    p[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }
}
ull getHash(int l, int r) { return h[r] - h[l-1] * p[r - l + 1]; }

int main() {
    string text, pattern;
    cin >> text >> pattern;
    initHash(text);
    int n = text.size(), m = pattern.size();

    // 算pattern的哈希
    ull patHash = 0;
    for (char c : pattern) patHash = patHash * P + c;

    int cnt = 0;
    for (int i = 1; i + m - 1 <= n; i++)
        if (getHash(i, i + m - 1) == patHash) cnt++;   // 子串哈希==模式哈希
    cout << cnt << "\n";
    return 0;
}

第 5 题：最长重复子串（哈希 + 二分 —— 经典综合，有难度）

题意：给一个字符串 s，求最长的、在 s 中出现至少两次的子串的长度（可重叠）。

输入样例
banana

输出样例
3

（"ana" 出现两次（位置1和3），长度3；没有更长的重复子串）

考点：哈希 + 二分答案（接 1.2）。二分子串长度 len，用哈希检查"是否存在长度为 len 的重复子串"（把所有长度 len 的子串哈希存 set，有重复说明存在）。长度满足单调性（长度 len 可行则更短的也可行）。练习"二分答案 + 哈希验证"这个经典组合。 想不出可看答案。

提示：① 二分子串长度 len（范围 [1, n-1]）；② check(len)：枚举所有长度 len 的子串求哈希存 set，如果出现重复哈希则返回 true；③ 最大化 len（接1.2最大值模板：可行往大走）；④ 这是"最大化最小值"类二分——长度越长越难找到重复，求最长可行长度。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const ull P = 131;
ull h[N], p[N];
int n;

ull getHash(int l, int r) { return h[r] - h[l-1] * p[r - l + 1]; }

bool check(int len) {       // 是否存在长度len的重复子串
    set<ull> st;
    for (int i = 1; i + len - 1 <= n; i++) {
        ull hsh = getHash(i, i + len - 1);
        if (st.count(hsh)) return true;   // 出现重复
        st.insert(hsh);
    }
    return false;
}

int main() {
    string s;
    cin >> s;
    n = s.size();
    p[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * P + s[i-1];
        p[i] = p[i-1] * P;
    }

    // 二分子串长度
    int l = 1, r = n - 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) { ans = mid; l = mid + 1; }  // 可行，往长了试
        else r = mid - 1;
    }
    cout << ans << "\n";
    return 0;
}

考点回顾：

1. 子串比较 —— 哈希模板
2. 不同子串个数 —— 哈希+set查重
3. 回文判断 —— 正反哈希
4. 模式串匹配 —— 哈希匹配
5. 最长重复子串 —— 哈希+二分

最该吃透的认知：

• 哈希模板（第1题）——前缀哈希 h[i]=h[i-1]×P+s[i-1] + 子串哈希 getHash(l,r)=h[r]-h[l-1]×p[r-l+1]。和前缀和一脉相承（多了位权 p）。这是字符串哈希的核心，必背。
• 哈希的通用性——比较子串(第1题)、查重(第2题)、回文(第3题)、匹配(第4题)，都能用哈希O(1)解决。哈希是字符串问题的"瑞士军刀"。
• 哈希+二分（第5题）——求"最长XX子串"的经典组合：二分长度，哈希验证。这个套路很常用（最长重复子串、最长公共子串等）。
• 回文的正反哈希（第3题）——正读哈希==反读哈希则回文，关键是反串下标对应。

核心记忆——哈希模板：

h[i] = h[i-1]*P + s[i-1];          // 前缀哈希
p[i] = p[i-1]*P;                    // 幂
getHash(l,r) = h[r] - h[l-1]*p[r-l+1];  // O(1)子串哈希
// ull自然溢出，P=131

把这个模板练熟，配合set查重、二分求最长，字符串哈希就够用了。

先抓住它解决的问题：

KMP = 在一个长文本串里，高效地找出一个短模式串出现的所有位置。
比如在 "ababcabab" 里找 "abab" 出现在哪。朴素做法会重复比较、O(n×m)；KMP 通过预处理模式串自身的信息，避免重复比较，达到 O(n+m)。

一、先理解朴素匹配的问题

朴素匹配：把模式串从文本串的每个位置开始逐字符比对。

文本: a b a b c a b a b
模式: a b a b

朴素做法：从文本位置0开始比 "abab" vs "abab"... 比到第5个字符 'c'≠模式的'a'（其实是模式已匹配完，这里举匹配失败的例子）。失败后，朴素做法把模式串右移一位，从文本位置1重新开始比 ——但这丢弃了已经比对过的信息，导致重复比较。

KMP 的改进：失败时，不从头开始，而是利用"已经匹配的部分"的信息，让模式串尽可能少地右移，跳过那些注定不匹配的位置。关键就是知道"失败后模式串该移到哪" ——这个信息存在 next 数组里。

二、核心：next 数组（最难理解的部分）

next 数组是什么

next[i] = 模式串前 i 个字符组成的子串中，"最长的相等前缀和后缀"的长度。

"前缀"指从开头开始的子串，"后缀"指到结尾结束的子串（都不包括整个串本身）。

举例：模式串 "ababc"，求每个位置的 next：

• "a"：没有相等的前后缀，next=0
• "ab"：前缀{a}，后缀{b}，不相等，next=0
• "aba"：前缀{a, ab}，后缀{a, ba}，"a"="a" 相等，最长1，next=1
• "abab"：前缀有"ab"，后缀有"ab"，相等，最长2，next=2
• "ababc"：找不到相等前后缀，next=0

所以 "ababc" 的 next 数组是 [0, 0, 1, 2, 0]。

next 数组的作用

当匹配在模式串第 i 位失败时，next[i-1] 告诉你：前面已经匹配的部分中，有长度为 next[i-1] 的前缀和后缀相等，所以可以直接把模式串移动，让那个前缀对齐到后缀的位置，从 next[i-1] 处继续比，不用从头开始。

这是 KMP 的精髓，也是最难理解的地方。直观理解：已经匹配的部分末尾有一段（后缀）和模式串开头一段（前缀）相同，那失败后这段开头不用重新比，直接接着比就行。next 数组记录的就是"可以复用多少已匹配的内容"。

理解 next 数组需要时间，初学先记住"next[i] = 最长相等前后缀长度"这个定义和它的作用，模板会用即可，深入理解可以慢慢来。

三、KMP 完整模板（背下来）

第一步：求模式串的 next 数组

// 求模式串 p 的 next 数组
vector<int> getNext(string p) {
    int m = p.size();
    vector<int> nxt(m, 0);
    int j = 0;                       // j 指向当前最长相等前后缀的末尾
    for (int i = 1; i < m; i++) {    // i 从1开始遍历
        while (j > 0 && p[i] != p[j])
            j = nxt[j-1];            // 不匹配，回退 j（利用之前的 next）
        if (p[i] == p[j]) j++;       // 匹配，前后缀长度+1
        nxt[i] = j;                  // 记录
    }
    return nxt;
}

第二步：用 next 数组在文本串中匹配

// 在文本 s 中找模式 p，返回所有出现的起始位置（0-indexed）
vector<int> kmp(string s, string p) {
    int n = s.size(), m = p.size();
    vector<int> nxt = getNext(p);
    vector<int> result;
    int j = 0;                       // j 指向模式串当前匹配到的位置
    for (int i = 0; i < n; i++) {    // i 遍历文本串
        while (j > 0 && s[i] != p[j])
            j = nxt[j-1];            // 失配，j 回退（KMP 的核心，不回退 i）
        if (s[i] == p[j]) j++;       // 匹配，j 前进
        if (j == m) {                // 完全匹配（模式串走完）
            result.push_back(i - m + 1);   // 记录起始位置
            j = nxt[j-1];            // 继续找下一个匹配
        }
    }
    return result;
}

关键点拆解：

• j = nxt[j-1]：失配时，j 回退到 next 指示的位置（复用已匹配的前缀），而 i 不回退——这是 KMP 高效的关键，文本指针 i 只前进不后退，所以 O(n)。
• j == m 时找到一个匹配：模式串完全匹配，记录位置 i-m+1（起始下标），然后 j = nxt[j-1] 继续找后面的匹配。
• getNext 和 kmp 的结构几乎一样：都是"失配回退 j、匹配前进 j"，因为求 next 本质是"模式串自己和自己匹配"。

KMP 模板要背熟。理解的核心：i（文本指针）永不回退，失配时只回退 j（模式指针）到 next 指示的位置，从而避免重复比较，O(n+m)。next 数组的求法和匹配过程结构相同。

四、KMP 的应用

应用 1：字符串匹配（找模式串位置）

直接用上面的 kmp 函数，返回所有出现位置。这是 KMP 的本职工作。

应用 2：统计模式串出现次数

kmp 返回的 result 的大小就是出现次数。

应用 3：next 数组的其他用途

next 数组本身有用，比如：

• 求字符串的最小循环节：如果 n % (n - next[n-1]) == 0，则 n - next[n-1] 是最小循环节长度。（如 "abcabc" 的循环节是 "abc"）
• 判断字符串的周期性。

KMP 不仅能匹配，next 数组还能解决循环节、周期等问题。铜牌阶段，会用 KMP 做字符串匹配是基本要求，next 的高级应用了解即可。

五、KMP vs 字符串哈希（怎么选）

字符串匹配既能用 KMP 也能用哈希（6.1），怎么选：

单纯字符串匹配，两者都行。KMP 稳定正确、O(n+m) 有保证；哈希更灵活、好写但有冲突风险。铜牌阶段，简单匹配用哈希也行（你已经会了），但 KMP 作为经典算法要掌握，尤其它的 next 数组能解决哈希不好处理的循环节问题。

六、KMP 解题思维

1. 识别：字符串匹配（找子串位置/次数）、求循环节/周期 → KMP。
2. 求 next 数组：预处理模式串。
3. 匹配：用 next 数组在文本串中匹配，i 不回退。
4. 应用 next：循环节、周期等。

七、本节速记卡

• KMP：高效字符串匹配，在文本串找模式串，O(n+m)。
• 核心 next 数组：next[i] = 前 i 个字符的最长相等前后缀长度。
• 匹配关键：失配时 i（文本指针）不回退，只回退 j（模式指针）到 next 指示位置，复用已匹配内容，避免重复比较。
• 模板：getNext（求next，模式串自匹配）+ kmp（用next匹配）。两者结构相同（失配回退j、匹配进j）。
• 找到匹配：j == m 时记录位置 i-m+1，然后 j=next[j-1] 继续。
• next 高级用途：最小循环节 = n - next[n-1]（若 n 整除它）。
• vs 哈希：KMP 稳定正确，哈希灵活好写；匹配两者皆可，KMP 经典必会。

KMP 是字符串算法的经典基石。它的难点在于 next 数组的理解——初学先掌握模板会用，理解"i 不回退、j 回退复用"的核心思想，next 的深层原理可以通过多看几遍、画图模拟慢慢消化。模板背熟后，字符串匹配题就能稳定解决。

说实话，KMP 的 next 数组是这套课程里比较难理解的点之一，如果一时没完全吃透很正常。会用模板 + 知道它解决什么问题，对铜牌就够了。深入理解可以后续慢慢来。

下一节 6.3 Trie（字典树）——一种树形结构，高效存储和查询字符串集合，用于"前缀匹配""字符串查找"等。它比 KMP 直观，是字符串的最后一个核心内容。

配套练习题

好，给你 4 道 KMP 题，字符串匹配、出现次数、next数组应用、循环节。KMP 的 next 数组需要时间消化，先把模板用熟、感受它解决什么问题，理解可以慢慢来。

老规矩：先自己写，重点是把 KMP 模板用对、感受"i不回退只回退j"的机制，再展开对照。

第 1 题：字符串匹配（KMP 模板 —— 必会）

题意：给一个文本串 text 和模式串 pattern，求 pattern 在 text 中所有出现的起始位置（位置从1开始，按升序输出，可重叠）。如果没出现，输出 -1。

输入样例
ababcabab
ab

输出样例
1 3 6 8

（"ab" 在位置1、3、6、8出现，下标从1）

考点：KMP 标准模板。求 next 数组 + 用 next 匹配。找到匹配（j==m）记录位置。这是 KMP 的本职工作，模板要会用。

#include <bits/stdc++.h>
using namespace std;

vector<int> getNext(string p) {
    int m = p.size();
    vector<int> nxt(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = nxt[j-1];
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}

int main() {
    string s, p;
    cin >> s >> p;
    int n = s.size(), m = p.size();
    vector<int> nxt = getNext(p);
    vector<int> result;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) j = nxt[j-1];   // 失配，回退j
        if (s[i] == p[j]) j++;
        if (j == m) {                  // 完全匹配
            result.push_back(i - m + 2);   // 起始位置(1-indexed)
            j = nxt[j-1];              // 继续找
        }
    }
    if (result.empty()) cout << -1 << "\n";
    else {
        for (int x : result) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

第 2 题：模式串出现次数（KMP 计数）

题意：给文本串 text 和模式串 pattern，求 pattern 在 text 中出现的次数（可重叠）。

输入样例
aaaa
aa

输出样例
3

（"aa" 在 "aaaa" 中出现3次：位置0,1,2。注意可重叠）

考点：KMP 匹配，统计 j==m 的次数。练习 KMP 计数，注意可重叠的情况（找到一个匹配后 j=next[j-1] 继续，而不是从头）。

提示：和第1题一样跑KMP，每次 j==m 时计数器+1，然后 j=next[j-1] 继续找。这个回退保证了重叠匹配能被找到（如aaaa找aa）。

#include <bits/stdc++.h>
using namespace std;

vector<int> getNext(string p) {
    int m = p.size();
    vector<int> nxt(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = nxt[j-1];
        if (p[i] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}

int main() {
    string s, p;
    cin >> s >> p;
    int n = s.size(), m = p.size();
    vector<int> nxt = getNext(p);
    int j = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) j = nxt[j-1];
        if (s[i] == p[j]) j++;
        if (j == m) {
            cnt++;                     // 计数
            j = nxt[j-1];              // 回退继续（保证重叠匹配）
        }
    }
    cout << cnt << "\n";
    return 0;
}

第 3 题：求 next 数组（理解 next —— 基础）

题意：给一个字符串 s，输出它的 next 数组（即每个前缀的最长相等前后缀长度）。

输入样例
ababa

输出样例
0 0 1 2 3

（"a":0, "ab":0, "aba":1(a), "abab":2(ab), "ababa":3(aba)）

考点：单独求 next 数组，加深对 next 含义的理解。next[i] = 前 i+1 个字符的最长相等前后缀长度。练习理解 next 数组本身。

提示：就是 getNext 函数。理解每个值的含义——"aba"的next是1，因为前缀"a"和后缀"a"相等，长度1；"ababa"的next是3，因为前缀"aba"和后缀"aba"相等。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> nxt(n, 0);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = nxt[j-1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    for (int i = 0; i < n; i++) cout << nxt[i] << " ";
    cout << "\n";
    return 0;
}

第 4 题：最小循环节（next 应用 —— 经典，有难度）

题意：给一个字符串 s，求它的最小循环节长度。如果 s 是由某个子串重复若干次（至少2次）拼成的，输出最小循环节长度；如果不是周期串（不能由更小的串重复构成），输出字符串长度本身。

输入样例
abcabcabc

输出样例
3

（"abcabcabc" = "abc" 重复3次，最小循环节长度3）

输入样例
abcab

输出样例
5

（"abcab" 不能由更小的串重复构成，输出长度5）

考点：next 数组的经典应用——求循环节。设 n 为字符串长度，len = n - next[n-1]（next[n-1]是整个串的最长相等前后缀）。如果 n % len == 0 且 len < n，则 len 是最小循环节；否则整个串就是"循环节"（无更小周期），输出 n。 想不出可看答案理解这个结论。

提示：① 求 next 数组；② len = n - next[n-1]；③ 如果 n % len == 0，说明 s 由长度 len 的子串重复 n/len 次构成，输出 len；④ 否则输出 n（不是周期串）。理解：next[n-1] 是最长相等前后缀，n 减去它就是"错位长度"，恰好是循环节。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> nxt(n, 0);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = nxt[j-1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    int len = n - nxt[n-1];      // 错位长度 = 候选循环节
    if (n % len == 0) cout << len << "\n";   // 能整除，是周期串
    else cout << n << "\n";                   // 不能，无更小周期
    return 0;
}

考点回顾：

1. 字符串匹配 —— KMP模板
2. 出现次数 —— KMP计数（重叠）
3. 求next数组 —— 理解next
4. 最小循环节 —— next应用

最该吃透的认知：

• KMP模板（第1题）——getNext + 主匹配。核心是"i不回退、失配只回退j到next指示位置"，复用已匹配内容，O(n+m)。模板会用就行。
• 重叠匹配（第2题）——找到匹配后 j=next[j-1] 而非 j=0，保证重叠的匹配能被找到。这是KMP计数的细节。
• next数组的含义（第3题）——最长相等前后缀长度。多看例子加深理解，这是KMP最难懂的部分，慢慢消化。
• 循环节（第4题）——n-next[n-1] 是周期长度，整除则是循环节。这是next数组最经典的应用。

关于KMP的实话：next数组的原理确实是这套课程里较难理解的点。铜牌阶段，会用模板 + 知道它解决字符串匹配和循环节就够了，深层原理（为什么失配回退到next[j-1]是对的）可以后续通过画图模拟慢慢理解，不用急。很多人也是先会用、后理解。

而且——简单的字符串匹配你也可以用哈希（6.1）做，哈希更直观。KMP的不可替代价值在于next数组能解决循环节、周期这类问题。所以两个都掌握，各有用处。

核心记忆——KMP模板：

// getNext: 失配 j=nxt[j-1]，匹配 j++，记录 nxt[i]=j
// 匹配: i不回退，失配 j=nxt[j-1]，匹配 j++，j==m时找到
// 循环节: len = n - nxt[n-1]，n%len==0 则 len 是循环节

先抓住本质：

Trie（字典树/前缀树）= 把多个字符串的公共前缀合并存储的树形结构。
每个节点代表一个字符，从根到某节点的路径就拼成一个前缀。它能高效地"插入字符串""查询字符串是否存在""统计有某个前缀的字符串个数"。

一、Trie 的结构（直观理解）

想象把一堆单词存进一棵树：公共前缀只存一次，共享路径。

比如存 ["cat", "car", "card", "dog"]：

        根
       /  \
      c    d
      |    |
      a    o
     / \   |
    t   r  g
        |
        d

• "cat"、"car"、"card" 共享前缀 "ca"，所以 "ca" 这条路径只存一次，到 'a' 后分叉。
• "car" 和 "card" 共享 "car"，"card" 在 'r' 后继续接 'd'。
• "dog" 完全独立，单独一条路径。

每个节点的关键信息：

• 指向子节点的指针（26 个，对应 a~z）：表示从这个节点能接哪些字符。
• 是否是单词结尾的标记：因为 "car" 是单词，但它也是 "card" 的前缀，要标记 'r' 这个节点是一个单词的结尾。

Trie 的核心思想：用树的路径表示字符串，公共前缀共享节点。查一个字符串就是从根开始沿着字符往下走，省去了重复存储前缀的空间，查询也快。

二、Trie 的实现（数组版，竞赛常用）

竞赛里常用二维数组实现 Trie（比指针好写）：

const int N = 1e5 + 5;        // 最多节点数（所有字符串总长度）
int trie[N][26];              // trie[u][c] = 节点u通过字符c到达的子节点编号
bool isEnd[N];                // isEnd[u] = 节点u是否是某个单词的结尾
int cnt = 0;                  // 节点计数器（0是根节点）

// 插入一个字符串
void insert(string s) {
    int u = 0;                // 从根节点开始
    for (char ch : s) {
        int c = ch - 'a';     // 字符转0~25（接0.2字符技巧）
        if (trie[u][c] == 0)  // 如果没有这个子节点
            trie[u][c] = ++cnt;   // 创建新节点
        u = trie[u][c];       // 移动到子节点
    }
    isEnd[u] = true;          // 标记单词结尾
}

// 查询字符串是否存在
bool search(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) return false;   // 路径断了，不存在
        u = trie[u][c];
    }
    return isEnd[u];          // 必须是单词结尾才算存在
}

关键点拆解：

• trie[u][c]：节点 u 通过字符 c（0~25）能到达的子节点编号。0 表示没有这个子节点。
• 插入：沿字符往下走，没有节点就创建，最后标记结尾。
• 查询：沿字符走，路径断了就不存在；走到底还要检查 isEnd（因为可能只是某个词的前缀，不是完整单词）。
• ch - 'a'：字符转 0~25 的下标（接 0.2 / string 章节）。

数组版 Trie 是竞赛标配，比指针实现好写、不易出错。trie[u][c] 这个二维数组是核心：第一维是节点编号，第二维是字符。理解"插入沿路径建节点、查询沿路径走"即可。

三、Trie 的核心操作

操作 1：插入（insert）

如上，沿字符路径往下，缺节点就建，末尾标记 isEnd。

操作 2：查询完整单词（search）

如上，沿路径走，最后检查 isEnd。

操作 3：查询前缀（startsWith）

这是 Trie 的招牌能力——查"有没有以某个字符串为前缀的单词"。和 search 几乎一样，但不检查 isEnd（只要路径存在就行）：

// 查询是否有以 prefix 为前缀的单词
bool startsWith(string prefix) {
    int u = 0;
    for (char ch : prefix) {
        int c = ch - 'a';
        if (trie[u][c] == 0) return false;
        u = trie[u][c];
    }
    return true;              // 路径存在即可（不要求是完整单词）
}

操作 4：统计前缀出现次数（常见扩展）

给每个节点加一个计数，记录有多少个单词经过这个节点，就能统计"有多少个单词以某前缀开头"：

int passCnt[N];              // passCnt[u] = 经过节点u的单词数

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++cnt;
        u = trie[u][c];
        passCnt[u]++;         // 经过这个节点的单词数+1
    }
    isEnd[u] = true;
}

// 查询有多少单词以 prefix 开头
int countPrefix(string prefix) {
    int u = 0;
    for (char ch : prefix) {
        int c = ch - 'a';
        if (trie[u][c] == 0) return 0;
        u = trie[u][c];
    }
    return passCnt[u];        // 经过prefix最后一个节点的单词数
}

统计前缀数是 Trie 的经典扩展——在节点上维护"经过次数"，就能 O(前缀长度) 回答"多少单词有这个前缀"。这是 Trie 比哈希、KMP 更擅长的地方。

四、Trie 的典型应用

• 字符串集合的存储与查询：存一堆单词，快速查某个词在不在。
• 前缀匹配（招牌）：查有没有/有多少单词以某前缀开头（自动补全、词典）。
• 统计字符串出现次数：节点加计数。
• 01-Trie（拓展）：把数字按二进制位存进 Trie，用于求"异或最大值"等问题（铜牌少见，了解）。
• 多模式串匹配的基础：AC 自动机基于 Trie（拓展内容）。

Trie 的核心优势是前缀操作——任何涉及"公共前缀""以...开头""字符串集合查询"的问题，Trie 都很合适。

五、Trie 的复杂度与空间

• 插入/查询：O(字符串长度)，和集合里有多少字符串无关——很高效。
• 空间：O(总字符数 × 字符集大小)。trie[N][26] 中 N 要开到所有字符串的总长度。注意空间：如果字符串很多很长，N×26 可能很大，留意 MLE（接 0.4）。

六、Trie 解题思维

1. 识别：涉及字符串集合 + 前缀操作 + 查询是否存在/统计 → Trie。关键词：前缀、以...开头、字典、自动补全、单词查询。
2. 建 Trie：trie[N][26] 数组，insert 插入所有字符串。
3. 查询：search（完整单词）或 startsWith（前缀），按需在节点维护计数。
4. 注意空间：N 开到总字符数。

七、本节速记卡

• Trie（字典树）：树形结构存字符串集合，公共前缀共享节点，擅长前缀操作。
• 结构：trie[u][c] = 节点u经字符c到的子节点；isEnd[u] = 是否单词结尾。
• 插入：沿字符路径走，缺节点就建（++cnt），末尾标 isEnd。
• 查询单词：沿路径走，最后检查 isEnd。
• 查询前缀（招牌）：沿路径走，不查 isEnd，路径存在即可。
• 统计前缀数：节点维护 passCnt（经过的单词数）。
• 复杂度：插入/查询 O(串长)，与集合大小无关。空间 O(总字符数×26)，注意 MLE。
• 应用：字符串集合查询、前缀匹配、自动补全、出现次数统计。
• 识别：字符串集合 + 前缀/以...开头/字典查询。

Trie 是处理"字符串集合 + 前缀"问题的利器，而且比 KMP 直观好懂——就是把字符串存成共享前缀的树。核心是 trie[u][c] 数组和"插入建节点、查询走路径"的操作。前缀统计是它的招牌，是哈希和 KMP 不好处理的。

它的实现简单（数组版就十几行核心代码），应用明确（前缀相关），是字符串里相对好掌握的内容。

🎉 第六部分：字符串 的核心内容完成！ 回顾字符串之路：

• 6.1 字符串哈希（O(1) 比较子串，瑞士军刀）
• 6.2 KMP（字符串匹配，next 数组）
• 6.3 Trie（字典树，前缀操作）

（6.4 Manacher/AC自动机/后缀结构是拓展，铜牌阶段可不学。）

字符串三大基础工具到手了：哈希（比较子串）、KMP（匹配+循环节）、Trie（前缀+集合）。铜牌阶段字符串题大多能用这三个应对。

按大纲，最后还剩 第七部分：进阶数据结构（树状数组、线段树入门）。这是铜牌的最后一块拼图——树状数组能高效处理"单点修改+区间查询",是性价比较高的数据结构。

配套练习题

好，给你 4 道 Trie 题，字符串查询、前缀统计、自动补全。Trie 比较直观，把"插入建节点、查询走路径"的模板练熟即可。

老规矩：先自己写，重点想清楚"查完整单词还是查前缀、节点上要不要维护计数",再展开对照。

第 1 题：字符串集合查询（Trie 模板 —— 必会）

题意：维护一个字符串集合，支持两种操作：

• 1 s：把字符串 s 插入集合。
• 2 s：查询字符串 s 是否在集合中（在输出 YES，否则 NO）。

字符串只含小写字母。

输入样例
5
1 apple
1 app
2 apple
2 appl
2 app

输出样例
YES
NO
YES

（插入apple、app；查apple在→YES；查appl不在（只是前缀，没单独插入）→NO；查app在→YES）

考点：Trie 模板。insert 插入 + search 查询（查完整单词要检查 isEnd）。注意 "appl" 虽是前缀但没作为完整单词插入，所以查询返回NO。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int trie[N][26];
bool isEnd[N];
int cnt = 0;

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++cnt;
        u = trie[u][c];
    }
    isEnd[u] = true;
}

bool search(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) return false;
        u = trie[u][c];
    }
    return isEnd[u];           // 必须是单词结尾
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        int op;
        string s;
        cin >> op >> s;
        if (op == 1) insert(s);
        else cout << (search(s) ? "YES" : "NO") << "\n";
    }
    return 0;
}

第 2 题：前缀统计（Trie + 计数 —— 招牌应用）

题意：先插入 n 个字符串，然后 q 次询问，每次给一个前缀 p，问集合中有多少个字符串以 p 为前缀。

输入样例
4 3
apple
app
apricot
banana
ap
app
ban

输出样例
3
2
1

（以"ap"为前缀的：apple,app,apricot 共3个；以"app"为前缀的：apple,app 共2个；以"ban"为前缀的：banana 共1个）

考点：Trie 的招牌应用——前缀统计。在每个节点维护 passCnt（经过该节点的字符串数），查询前缀时返回前缀最后一个节点的 passCnt。练习"节点维护经过计数"。

提示：① insert 时每经过一个节点 passCnt[u]++；② 查询前缀走到最后一个节点，返回 passCnt[u]；③ 路径断了返回0。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int trie[N][26];
int passCnt[N];           // 经过节点的字符串数
int cnt = 0;

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++cnt;
        u = trie[u][c];
        passCnt[u]++;          // 经过+1
    }
}

int countPrefix(string p) {
    int u = 0;
    for (char ch : p) {
        int c = ch - 'a';
        if (trie[u][c] == 0) return 0;   // 路径断了
        u = trie[u][c];
    }
    return passCnt[u];         // 经过前缀末节点的字符串数
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        insert(s);
    }
    while (q--) {
        string p; cin >> p;
        cout << countPrefix(p) << "\n";
    }
    return 0;
}

第 3 题：最长公共前缀（Trie 应用 —— 变体）

题意：给 n 个字符串，求所有字符串的最长公共前缀长度。

输入样例
3
flower
flow
flight

输出样例
2

（flower,flow,flight 的公共前缀是 "fl"，长度2）

考点：可以用 Trie——把所有字符串插入，然后从根往下走，只要某个节点只有一个子节点且不是某个串的结尾，就继续往下，统计深度。练习用 Trie 求公共前缀。 （注：这题也可以不用Trie直接逐字符比，但用Trie是个好练习。）

提示：① 插入所有字符串，节点维护 passCnt 和 isEnd；② 从根往下走，当前节点如果恰好只有1个子节点 且 当前不是任何单词的结尾（passCnt等于总串数说明所有串都经过），就继续，深度+1；③ 一旦分叉（多个子节点）或到达某单词结尾就停。或者更简单：直接逐字符比较所有串，不一定要用Trie。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int trie[N][26];
int passCnt[N];
bool isEnd[N];
int cnt = 0, n;

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++cnt;
        u = trie[u][c];
        passCnt[u]++;
    }
    isEnd[u] = true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        insert(s);
    }
    // 从根往下走，只要所有串都经过当前节点且不分叉
    int u = 0, depth = 0;
    while (true) {
        int next = -1, children = 0;
        for (int c = 0; c < 26; c++)
            if (trie[u][c] && passCnt[trie[u][c]] == n) {  // 所有串都经过
                next = trie[u][c];
                children++;
            }
        if (children == 1 && !isEnd[next]) {   // 只有一条路且不是单词结尾
            depth++;
            u = next;
        } else if (children == 1 && isEnd[next]) {
            depth++;        // 是结尾但所有串都经过，说明这个串是其他串前缀
            break;
        } else break;       // 分叉或无路
    }
    cout << depth << "\n";
    return 0;
}

第 4 题：自动补全/搜索建议（Trie 综合 —— 有难度）

题意：给 n 个单词（词典），然后 q 次查询，每次给一个前缀 p，输出词典中以 p 为前缀的字典序最小的那个单词。如果没有以 p 为前缀的单词，输出 NONE。

输入样例
4 3
apple
application
apply
banana
app
appl
ban

输出样例
apple
apple
banana

（以"app"为前缀的字典序最小是apple（apple < application < apply）；以"appl"为前缀的最小也是apple；以"ban"为前缀的是banana）

考点：Trie + DFS 找字典序最小。先沿前缀走到对应节点，然后从该节点开始 DFS，每次优先走字典序最小的子节点（从'a'到'z'），找到第一个 isEnd 的单词就是字典序最小的。练习"Trie上DFS找特定单词"。 想不出可看答案。

提示：① 沿前缀走到节点 u（走不通输出NONE）；② 从 u 开始 DFS，按 'a'~'z' 顺序尝试子节点（保证字典序）；③ 沿途记录路径字符，遇到第一个 isEnd 就是答案（前缀+DFS路径）。注意前缀本身可能就是一个单词。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int trie[N][26];
bool isEnd[N];
int cnt = 0;

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++cnt;
        u = trie[u][c];
    }
    isEnd[u] = true;
}

// 从节点u开始DFS找字典序最小的单词，path是已走的字符
bool dfs(int u, string& path) {
    if (isEnd[u]) return true;     // 找到一个单词
    for (int c = 0; c < 26; c++) {  // 按字典序'a'~'z'
        if (trie[u][c]) {
            path += ('a' + c);
            if (dfs(trie[u][c], path)) return true;
            path.pop_back();        // 回溯
        }
    }
    return false;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        insert(s);
    }
    while (q--) {
        string p; cin >> p;
        // 先沿前缀走
        int u = 0;
        bool ok = true;
        for (char ch : p) {
            int c = ch - 'a';
            if (trie[u][c] == 0) { ok = false; break; }
            u = trie[u][c];
        }
        if (!ok) { cout << "NONE\n"; continue; }
        // 从前缀末节点DFS找字典序最小
        string suffix = "";
        dfs(u, suffix);
        cout << p + suffix << "\n";   // 前缀+DFS路径
    }
    return 0;
}

考点回顾：

1. 集合查询 —— Trie模板（查isEnd）
2. 前缀统计 —— 节点维护passCnt（招牌）
3. 最长公共前缀 —— Trie应用
4. 自动补全 —— Trie+DFS

最该吃透的认知：

• Trie模板（第1题）——trie[u][c]数组 + insert建节点 + search走路径。查完整单词检查isEnd，查前缀不检查——这是关键区别。
• 前缀统计（第2题）——节点维护passCnt（经过计数），是Trie最招牌、最常用的应用。"有多少串以X为前缀"= passCnt[X末节点]。
• Trie+DFS（第4题）——从某节点DFS、按字典序遍历子节点，能找特定单词（如字典序最小）。这是Trie的进阶用法。
• 何时用Trie——字符串集合 + 前缀操作。前缀统计、自动补全是Trie比哈希/KMP更擅长的场景。

核心记忆——Trie模板：

// insert: 沿字符走，trie[u][c]==0就++cnt建节点，末尾isEnd[u]=true
// search: 沿字符走，断了return false，最后return isEnd[u]
// 前缀统计: insert时passCnt[u]++，查询返回passCnt[末节点]

把这个练熟，前缀相关的字符串题就能用Trie解决。

🎉 第六部分：字符串 全部完成！（哈希、KMP、Trie三大工具到手）