第 8 章字符串

本章定位：按 realp/考点分析与预测.md 的统计，近十年 48 道题里算作字符串的只有 3 道，其中真正要用字符串算法的只有 2020 年 T2 一道；2023 年、2024 年的 T1 只是拿字符串当外壳，做法是贪心和数字符。但 T1 是必须拿满的题，所以这一章的重点在两头：8.1（读入、遍历、比较、数字符不出错）和 8.6（近年的字符串题到底怎么做）。中间的哈希和 KMP 能照着模板写出来就够，Trie 和它后面的内容了解即可。

8.1 字符串基础【必会】

一句话：字符串有 string 和 char 数组两种存法，要会读、会遍历、会比较、会数每种字符的个数。 识别信号：题面出现“字符串”“小写字母”“01 串”“字典序”。

string s;
cin >> s;                 // 读一个不含空格的串。下标从 0 开始，长度是 s.size()

char t[N];                // N 取“最大长度 + 5”：从 t[1] 开始存，末尾还要放一个 '\0'
cin >> (t + 1);           // 从 t[1] 开始存，下标就是 1..n
int n = strlen(t + 1);    // 长度。strlen 每调用一次都把整个串扫一遍，所以只调一次、存进 n

怎么选：串很长（10⁵ 以上）、要按下标逐个处理、要配合下标从 1 开始的数组（哈希、KMP 的模板）时，用 char 数组；要拼接、排序、去重、放进 vector 或者当 map 的键时，用 string。一道题里选定一种，不要混用。

string 的常用操作和代价：

操作	写法	复杂度
长度	`s.size()`	O(1)
末尾加一个字符	`s += c`	O(1)
拼接两个串	`s + t`	O(两串长度之和)
取子串	`s.substr(pos, len)`：从下标 pos 开始取 len 个	O(len)
查找	`s.find(t)`：返回第一次出现的下标，找不到返回 `string::npos`	最坏 O(n × m)
比较	`s == t`、`s < t`（按字典序）	O(较短的长度)
排序、翻转	`sort(s.begin(), s.end())`、`reverse(s.begin(), s.end())`	O(n log n)、O(n)
数字和字符串互转	`to_string(x)`、`stoi(s)`、`stoll(s)`	O(长度)

字符本身就是整数（ASCII 码），可以直接加减、比较、当下标：

int idx = c - 'a';                 // 小写字母 → 0..25；反过来是 char('a' + idx)
int digit = c - '0';               // 数字字符 → 0..9
int cnt[26] = {0};                 // 数每个字母出现了几次——近年字符串题里最常用的一招
for (int i = 1; i <= n; i++) cnt[t[i] - 'a']++;

字典序：从左到右逐位比较，第一个不同的位置上，字符小的那个串小；如果一直相同直到其中一个串结束，短的小。

"abc" < "abd"（第 3 位 c < d）；"ab" < "abc"（前面都相同，短的小）；"b" > "abc"（第 1 位就分出了大小，长度不起作用）。
"10" < "9"：第 1 位 '1' < '9'。所以数字串不能直接按字典序比大小，只有长度相同时两者才一致。
数字 < 大写字母 < 小写字母（'0' 是 48，'A' 是 65，'a' 是 97），所以 "Z" < "a"。
想让一个串的字典序尽量小，就让越靠前的位置越小——前面的位置优先级高。字符串贪心大多从这句话出发。

易错点

for (int i = 0; i < strlen(t); i++)：每转一圈都重新算一次长度，整个循环变成 O(n²)，n = 10⁵ 就超时。
s = s + c 每次都把整个串复制一遍，循环里这么写是 O(n²)；s += c 才是 O(1)。循环里反复 substr、erase、insert 也一样。
s.size() 是无符号数。空串的 s.size() - 1 不是 -1，而是 18446744073709551615，for (int i = 0; i < s.size() - 1; i++) 就会越界。先写 int n = s.size();，后面都用 n。
s.substr(pos, len) 的第二个参数是长度，不是右端点。
char 数组不能用 == 比较（比的是地址），要用 strcmp(a, b) == 0。
读单个字符用 cin >> c（c 是 char）：它会自动跳过空格和换行，读到的是下一个看得见的字符。getchar() 不跳空白，而且关了同步以后不能和 cin 混用（0.4 节），不要用它。
01 串、一长串数字要读成字符串（string 或 char 数组），再逐个 - '0'；读进整数变量会把整串当成一个数。
cin >> n 之后用 getline 读一整行，第一次读到的是 n 后面剩下的空行。能用 cin >> s 就不用 getline。
长串照样用 cin 读，前提是 main 开头写了关同步的两行（0.4 节）。实测读一个 200 万字符的串只要 0.004 秒，没写那两行是 0.03 秒。多组数据时 cnt 数组每组都要清零（0.6 节）。

练一练：洛谷 P1125 [NOIP2008 提高组] 笨小猴（数字符）；P1308 [NOIP2011 普及组] 统计单词数（要读带空格的一整行）。

8.2 字符串哈希【常考】

一句话：把字符串换算成一个整数，“两个子串是否相同”就变成“两个整数是否相等”，O(1) 回答。 识别信号：多次问“这两段是否相同”；“有多少个不同的串”；判断循环节、回文；想不起 KMP 时的替代办法。 复杂度：预处理 O(n)，每次取一个子串的哈希值 O(1)。

// 字符串哈希：预处理后 O(1) 判断两个子串是否相等。
// 输入：一行字符串 s，一行 q，然后 q 行 l1 r1 l2 r2（下标从 1 开始）；s[l1..r1] 与 s[l2..r2] 相等输出 Yes，否则 No。
// 把字符串看成一个 BASE 进制的大数，用 unsigned long long 存，溢出就让它溢出（相当于对 2^64 取模）。
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 1000005;
const ull BASE = 131;
char s[N];
ull h[N], pw[N];  // h[i]：前 i 个字符的哈希值；pw[i] = BASE 的 i 次方

ull get(int l, int r) {  // 子串 s[l..r] 的哈希值：从 h[r] 里减掉前 l-1 个字符的部分
    return h[r] - h[l - 1] * pw[r - l + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> (s + 1);  // 从 s[1] 开始存
    int n = strlen(s + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * BASE;
        h[i] = h[i - 1] * BASE + s[i];  // 字符直接用它的 ASCII 码，不会是 0
    }
    int q;
    cin >> q;
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        bool same = (r1 - l1 == r2 - l2) && get(l1, r1) == get(l2, r2);  // 长度不同直接不相等
        cout << (same ? "Yes" : "No") << '\n';
    }
    return 0;
}

原理和十进制数一样。把 "abc" 看成一个 131 进制的数，每个字符是一位：'a' × 131² + 'b' × 131 + 'c'。h[i] 是前 i 个字符组成的数，所以 h[i] = h[i-1] × 131 + s[i]。取子串好比从 12345 里取出后三位：12345 − 12 × 1000 = 345——把前面的部分乘上进位对齐，再减掉。

会不会撞：两个不同的串算出同一个值，叫冲突。unsigned long long 溢出后相当于自动对 2⁶⁴ 取模，值有 1.8×10¹⁹ 种，随机数据下基本撞不上，但存在专门针对它构造的数据（换 BASE 也躲不开）。不放心就改成取模，并且用两个不同的模数各算一份，两份都相等才算相等（双哈希）：

const long long MOD = 1000000007;      // 取模的写法：h、pw、BASE 都换成 long long，三处都要 % MOD
h[i] = (h[i - 1] * BASE + s[i]) % MOD;
pw[i] = pw[i - 1] * BASE % MOD;
long long get(int l, int r) { return ((h[r] - h[l - 1] * pw[r - l + 1]) % MOD + MOD) % MOD; }

只用一个 10⁹ 左右的模数是不够的：把 10⁵ 个不同的串放在一起判重，按概率几乎一定有两个撞上。

常见用法

判断 s 的两个子串是否相同：模板本身。
数有多少个不同的串：每个串算出整串的哈希值，排序后去重。
判断 len 是不是 s[1..L] 的循环节：get(1, L - len) == get(len + 1, L)（整体错开 len 位之后和自己重合）。
在 s 里找 t 的所有出现位置：算出 t 的哈希值，和 s 里每个长为 m 的子串比较，O(n)。KMP 忘了就用它。

易错点

h、pw 必须是 unsigned long long，中间不能混进 int 或 long long。全部模板里只有这一处该用 unsigned long long——这里要的就是它的自然溢出；别的地方（求和、计数、距离）一律 long long。
下标从 1 开始。get(l, r) 要用 h[l - 1]，从 0 开始存就会访问 h[-1]。
pw[0] = 1 别漏。
字符的值不能是 0。模板直接用 ASCII 码，没有问题；如果自己写成 s[i] - 'a'，'a' 就成了 0，"a" 和 "aa" 的哈希值都是 0。要写 s[i] - 'a' + 1。
数组不要起名叫 hash：和标准库里的 std::hash 重名，编译报错。
要互相比较的哈希值，必须用同一个 BASE、同一个模数算出来。

练一练：洛谷 P3370 【模板】字符串哈希。

8.3 KMP 【常考】

一句话：在长为 n 的文本串里找出长为 m 的模式串的所有出现位置，O(n + m)。 识别信号：“t 在 s 里出现了几次、出现在哪”；“最短循环节”；“最长的、既是前缀又是后缀的一段”。 复杂度：O(n + m)。

// KMP：在文本串 s1 里找出模式串 s2 的所有出现位置，O(n + m)。洛谷 P3375。
// nxt[i]：s2 的前 i 个字符里，最长的“既是前缀又是后缀”的长度（不能是整段自己），叫做 border。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
char s1[N], s2[N];
int nxt[N];  // 不要起名叫 next，会和标准库里的 std::next 冲突

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> (s1 + 1) >> (s2 + 1);  // 两个串都从下标 1 开始存
    int n = strlen(s1 + 1), m = strlen(s2 + 1);
    // 第一步：s2 自己和自己匹配，求出 nxt。j 是当前已经匹配上的长度
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && s2[i] != s2[j + 1]) j = nxt[j];  // 配不上：退到更短的 border 再试
        if (s2[i] == s2[j + 1]) j++;
        nxt[i] = j;
    }
    // 第二步：拿 s1 去匹配 s2，写法和上面几乎一样
    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && s1[i] != s2[j + 1]) j = nxt[j];
        if (s1[i] == s2[j + 1]) j++;
        if (j == m) {
            cout << i - m + 1 << '\n';  // s2 在 s1 里出现的起始位置
            j = nxt[j];                 // 退到 border 继续找，这样不会漏掉互相重叠的出现
        }
    }
    for (int i = 1; i <= m; i++) cout << nxt[i] << ' ';
    cout << '\n';
    return 0;
}

nxt 是什么：nxt[i] 是模式串前 i 个字符里，最长的“既是前缀、又是后缀”的那一段的长度（不能是这 i 个字符本身）。以 ABABC 为例：

i	1	2	3	4	5
前 i 个字符	A	AB	ABA	ABAB	ABABC
nxt[i]	0	0	1	2	0
那一段是	—	—	A	AB	—

为什么快：在 ABABABC 里找 ABABC。前 4 个字符 ABAB 都配上了（j = 4），第 5 个字符文本串是 A、模式串是 C，配不上。朴素做法是把模式串挪一格、从头再比；KMP 利用 nxt[4] = 2：已经配上的 ABAB，末尾的 AB 正好等于模式串开头的 AB，所以让 j 直接退到 2，接着拿模式串的第 3 个字符去比。文本串的指针 i 从不后退，所以总共只要 O(n + m)。

循环节：长为 n 的串，令 p = n − nxt[n]，p 就是最小的“整体错开 p 位后与自己重合”的长度。如果 n % p == 0，整个串恰好是前 p 个字符重复 n / p 次；否则它不能写成某一段的整数次重复。

串	n	nxt[n]	p = n − nxt[n]	结论
`abcabcabc`	9	6	3	9 % 3 == 0，是 `abc` 重复 3 次
`aaaa`	4	3	1	是 `a` 重复 4 次
`abcab`	5	2	3	5 % 3 ≠ 0，不是整数次重复（`abc` 重复后截掉了尾巴）
`abcd`	4	0	4	只能看成自己重复 1 次

易错点

求 nxt 的循环从 i = 2 开始，nxt[1] 固定是 0。从 1 开始的话，第一个字符会和自己配上，整个数组都错。
while (j > 0 && ...) 里的 j > 0 不能省。j 已经是 0 还配不上时，j = nxt[0] 还是 0，死循环。
比的是 s2[j + 1]，不是 s2[j]。j 是“已经配上的长度”，下一个要比的是第 j + 1 个字符。
找到一处之后写 j = nxt[j]，不是 j = 0。在 AAAA 里找 AA，正确答案是位置 1、2、3；写成 j = 0 只能找到 1 和 3。
两个串都从下标 1 开始存：cin >> (s + 1)，长度是 strlen(s + 1)。
数组不要起名叫 next：和标准库的 std::next 重名，编译报错。

练一练：洛谷 P3375 【模板】KMP；P4391 无线传输（循环节）；本系统 E16 echo。

8.4 Trie（字典树）【了解】

一句话：把一批字符串按公共前缀合并成一棵树，插入、查询一个串都只要 O(串长)。 识别信号：“有多少个串以它为前缀”；“这个串出现过没有”（这一种用 map<string, int> 或哈希也行）。 复杂度：每次 O(串长)；空间是结点数 × 字符集大小 × 4 字节。

// 字典树（Trie）：插入一批字符串，询问有多少个串以给定的串为前缀。洛谷 P8306（多组数据）。
// 每个结点代表一个前缀；cnt[p] 记录有多少个插入的串经过结点 p。
#include <bits/stdc++.h>
using namespace std;

const int N = 3000005;       // 结点数上限 = 所有串的总长度 + 1（根）
const int SIGMA = 62;        // 字符集大小：26 小写 + 26 大写 + 10 数字。空间 = N * SIGMA * 4 字节，先算再开
int ch[N][SIGMA], cnt[N], tot;  // ch[p][c]：从结点 p 沿字符 c 走到的儿子，0 表示没有；根是 0 号
char s[N];

int id(char c) {  // 把字符映射到 0..61
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 26;
    return c - '0' + 52;
}

void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int c = id(str[i]);
        if (!ch[p][c]) ch[p][c] = ++tot;  // 没有这个儿子就新建一个结点
        p = ch[p][c];
        cnt[p]++;  // 这个串经过了结点 p
    }
}

int query(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int c = id(str[i]);
        if (!ch[p][c]) return 0;  // 走不下去：没有任何串以它为前缀
        p = ch[p][c];
    }
    return cnt[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        // 多组数据：只清上一组用过的结点 0..tot。memset 整个数组的话，每组都要清几百 MB，必超时
        for (int i = 0; i <= tot; i++) {
            memset(ch[i], 0, sizeof ch[i]);
            cnt[i] = 0;
        }
        tot = 0;
        int n, q;
        cin >> n >> q;
        while (n--) {
            cin >> s;
            insert(s);
        }
        while (q--) {
            cin >> s;
            cout << query(s) << '\n';
        }
    }
    return 0;
}

根结点代表空串，从根往下每走一条边就多一个字符，所以每个结点代表一个前缀。插入 ab、ac、b 之后，树上有 5 个结点：根、a、ab、ac、b；结点 a 的 cnt 是 2（ab 和 ac 都经过它），所以“以 a 为前缀的串”有 2 个。

易错点

空间要先算再开。 结点数的上限是所有串的总长度。只有小写字母、总长 10⁶ 时是 10⁶ × 26 × 4 字节 = 104 MB；模板这道题总长 3×10⁶、字符集 62，数组是 744 MB——NOIP 常见的内存限制是 512 MB，这个规模在考场上开不下。
多组数据只清用过的结点（模板里的写法）。每组都 memset 整个数组，组数一多就超时。
cnt[p]++ 的位置决定了统计的是什么：写在循环里（每走一步加一次），数的是“有多少个串以它为前缀”；只在循环结束后给最后一个结点加一次，数的是“这个串本身出现了几次”。
0 既是根的编号，又表示“没有这个儿子”，所以新结点从 1 开始编号（++tot）。
id() 要覆盖题目里可能出现的所有字符。只有小写字母时就是 c - 'a'，SIGMA 改成 26。

练一练：洛谷 P8306 【模板】字典树；P2580 于是他错误的点名开始了。

8.5 Manacher 和 Z 函数【了解】

两个名字要认得，不要求会写：

Manacher：O(n) 求出以每个位置为中心的最长回文子串（洛谷 P3805）。
Z 函数（也叫扩展 KMP）：O(n) 求出 s 的每个后缀和 s 本身的最长公共前缀（洛谷 P5410）。

它们能做的事，哈希加二分大多也能做，只是多一个 log，拿部分分通常够用：

// 最长公共前缀：s[a..] 和 s[b..] 从头开始最多有多少个字符相同。二分长度，用哈希判断
int lcp(int a, int b) {
    int lo = 0, hi = n - max(a, b) + 1;   // 答案在 [lo, hi] 之间
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;      // 试一试“前 mid 个字符相同”
        if (get(a, a + mid - 1) == get(b, b + mid - 1)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

判断回文也可以用哈希：再从右往左算一份 hr[i] = hr[i + 1] * BASE + s[i]，那么 s[l..r] 倒着读的哈希值是 hr[l] - hr[r + 1] * pw[r - l + 1]，它和 get(l, r) 相等就是回文。

8.6 近年的字符串题到底在考什么【必会】

这一节会说出 NOIP 2023 T1、2024 T1 的做法。计划里的模拟考一、模拟考二还没做的话先跳过，考完再回来看。

年份	题目	看上去	实际做法
2020 T2	字符串匹配	把串拆成 (AB)(AB)…(AB)C	真正的字符串题：哈希或 Z 函数判断循环，再加树状数组计数
2023 T1	词典	字典序	贪心：每个单词只看它最小和最大的字符
2024 T1	编辑字符串	01 串上的交换操作	贪心：分段，数每段里 0 和 1 的个数

2023 T1 词典：n 个长度相同的单词，每个单词内部的字符可以任意交换；对每个单词问，能不能让它的字典序比其他所有单词都小。

// NOIP2023 T1 词典（洛谷 P9868）：字符串的外壳，实际是贪心。
// n 个长度为 m 的单词，每个单词内部的字符可以任意交换。对每个 i 问：能否让第 i 个单词的字典序严格小于其他所有单词？
// 让 w_i 尽量小：把它最小的字符换到最前面；让别的单词尽量大：把它们最大的字符换到最前面。
// 结论：w_i 的最小字符 < 其他每个单词的最大字符，就可以；否则不行。
#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
char word[N];
char smallest[N], largest[N];  // 第 i 个单词里最小、最大的字符

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> word;
        smallest[i] = largest[i] = word[0];
        for (int j = 1; j < m; j++) {
            smallest[i] = min(smallest[i], word[j]);
            largest[i] = max(largest[i], word[j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        bool ok = true;
        for (int j = 1; j <= n; j++)
            if (j != i && smallest[i] >= largest[j]) ok = false;  // 有一个单词压不过，就不行；相等也不行
        cout << (ok ? '1' : '0');
    }
    cout << '\n';
    return 0;
}

推导只有三步：

字符可以任意交换，所以一个单词能变成什么样，只取决于它有哪些字符。
字典序先看第一位。想让 w_i 尽量小，就把它最小的字符放到最前面；想让别的单词尽量大，就把它们最大的字符放到最前面。
于是只要比较“w_i 的最小字符”和“别的单词的最大字符”。两者相等时，w_i 的每个字符都不小于对方的每个字符，怎么排也赢不了，所以必须严格小于。

2024 T1 编辑字符串：两个 01 串，各有一些位置不许动，其余位置可以和相邻的可动位置交换；问最多能让多少个位置上两个串的字符相同。

相邻交换可以做任意多次，所以一段连续的可动位置里，字符可以随便重排——有用的信息只剩“这一段里有几个 0、几个 1”。不许动的位置自己单独算一段。
两个串各自分好段，给每个位置记下它属于哪一段，给每一段记下还剩几个 0、几个 1。
从左到右扫每个位置 i，看它在两个串里各属于哪一段：两段都还有 0，就各用掉一个 0，答案加 1；否则两段都还有 1，就各用掉一个 1，答案加 1；都不行，这个位置只能不同，两段各用掉自己剩下的那种字符。

整道题只有“分段”和“数个数”，没有用到任何字符串算法。

这类题怎么下手

先问：操作之后，什么变了、什么没变？“可以任意交换”意味着顺序没有用，只有每种字符的个数有用——开 cnt 数组。
要字典序最小，就从左到右一位一位定，每一位取当前能取到的最小的。
写代码之前，在纸上把样例手算一遍，确认自己理解的题意能算出样例的输出。
结论是猜的就要验证：n ≤ 8 时把所有排法都枚举出来（next_permutation），和贪心的结果对拍（0.10 节）。
字符串题和别的题一样有小数据档：串长只有几十、几百时，直接枚举所有拆法、用 substr 逐个比较就是暴力分。

练一练：模拟考之后，不看上面的代码重写一遍词典和编辑字符串；洛谷 P7114 [NOIP2020] 字符串匹配（只读题，想想串很短时怎么暴力）。

本章必会清单

两种读入各写一遍：cin >> s，以及 cin >> (t + 1) 配 strlen(t + 1)
用 cnt[26] 数出一个串里每个字母的个数；多组数据时记得清零
说出字典序的比较规则，并解释为什么 "10" 比 "9" 小
说出 8.1 里三种会超时的写法：循环条件里的 strlen、s = s + c、循环里的 substr
照着模板写出字符串哈希，说出 get(l, r) 的式子为什么要乘 pw[r - l + 1]
照着模板写出 KMP，交到洛谷 P3375 通过；说出循环节长度 n - nxt[n]
知道全局数组不能叫 next、hash
模拟考之后，不看题解把 NOIP2023 T1 词典重写一遍

第 8 章 字符串

8.1 字符串基础 【必会】

8.2 字符串哈希 【常考】

8.3 KMP 【常考】

8.4 Trie（字典树） 【了解】

8.5 Manacher 和 Z 函数 【了解】

8.6 近年的字符串题到底在考什么 【必会】

本章必会清单

第 8 章字符串

8.1 字符串基础【必会】

8.2 字符串哈希【常考】

8.4 Trie（字典树）【了解】

8.5 Manacher 和 Z 函数【了解】

8.6 近年的字符串题到底在考什么【必会】