String
自动关联目录:String
字符串问题的三个层次:
- 单串:在一个串里找结构(回文、周期、子串)
- 双串:两个串的关系(匹配、最长公共子串/子序列)
- 多串:一堆串的查询(Trie、AC 自动机、后缀数组)
字符串匹配
在文本(长)中找模式串(长)出现的位置。
暴力
for (int i = 0; i + m <= n; i++) {
bool ok = true;
for (int j = 0; j < m; j++)
if (T[i + j] != P[j]) { ok = false; break; }
if (ok) /* 在 i 处匹配 */;
}。最坏很慢,但实际数据下通常够快(因为常常很快就失配)。
KMP
核心思想:失配时不回退文本指针,利用模式串自身的重复结构跳到合适位置继续比。
前缀函数(next / failure 数组)
P = "ababaca"
π = [0, 0, 1, 2, 3, 0, 1]
i=2: "aba" 最长相等前后缀 = "a" 长度 1
i=3: "abab" = "ab" 长度 2
i=4: "ababa" = "aba" 长度 3
i=5: "ababac" 无 长度 0构造
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1]; // 回退
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
},每个字符最多被比较常数次。
匹配
vector<int> kmp(const string& T, const string& P) {
vector<int> pi = prefix_function(P);
vector<int> pos;
int j = 0;
for (int i = 0; i < (int)T.size(); i++) {
while (j > 0 && T[i] != P[j]) j = pi[j - 1];
if (T[i] == P[j]) j++;
if (j == (int)P.size()) {
pos.push_back(i - j + 1); // 匹配起点
j = pi[j - 1]; // 继续找下一个(允许重叠)
}
}
return pos;
}复杂度:。
KMP 的其他用途
- 求最短循环节:(若,则该长度是最小周期)
- 求所有 border(相等前后缀):沿 走
- 字符串最小表示法的一部分
Z 算法
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n, 0);
int l = 0, r = 0; // 当前最右的匹配区间 [l, r)
for (int i = 1; i < n; i++) {
if (i < r) z[i] = min(r - i, z[i - l]); // 利用已有信息
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}匹配:把 拼起来算 Z 数组, 的位置就是匹配点。
Z 算法 vs KMP:都。Z 更好理解,KMP 更省空间(不需要拼接)。
字符串哈希
见哈希章节。 但有碰撞风险。
竞赛共识:能用 KMP/Z 就用,哈希只作为"够用就好"的替代方案。
对比
| 算法 | 预处理 | 匹配 | 备注 |
|---|---|---|---|
| 暴力 | — | 实际常常够快 | |
| KMP | 经典,无碰撞 | ||
| Z 算法 | — | 更好写 | |
| 哈希 | 有碰撞风险 | ||
| 后缀数组 | 多串查询用 |
Trie(前缀树)
把一组字符串按前缀组织成树,用于快速查询"某个前缀是否存在""哪些串以某前缀开头"。
插入 "he", "she", "his", "hers"
root
│
h ───── s
/ \ \
e i h
/ \ \
* s e
/ * *
r
/
s
*
(* 表示单词结尾)struct Trie {
static const int N = 1e6 + 5, C = 26;
int ch[N][C], cnt[N], tot = 0;
Trie() { memset(ch, 0, sizeof ch); memset(cnt, 0, sizeof cnt); }
void insert(const string& s) {
int u = 0;
for (char c : s) {
int k = c - 'a';
if (!ch[u][k]) ch[u][k] = ++tot;
u = ch[u][k];
}
cnt[u]++; // 有几个串在此结尾
}
int query(const string& s) { // s 作为完整串出现几次
int u = 0;
for (char c : s) {
int k = c - 'a';
if (!ch[u][k]) return 0;
u = ch[u][k];
}
return cnt[u];
}
};复杂度:插入/查询。 空间:——这是主要缺点(字符集大时爆炸)。
变体:
- 01 Trie:字符集是,用于求最大异或值(贪心走相反的位)
- 压缩 Trie / Radix Tree:把单链压缩,省空间
- 持久化 Trie:支持历史版本查询
01 Trie 求最大异或对
// 对每个 x,在集合中找 y 使 x^y 最大
void insert(int x) {
int u = 0;
for (int i = 30; i >= 0; i--) {
int b = (x >> i) & 1;
if (!ch[u][b]) ch[u][b] = ++tot;
u = ch[u][b];
}
}
int query(int x) { // 返回最大异或值
int u = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int b = (x >> i) & 1;
if (ch[u][b ^ 1]) { // 走相反的位(贪心)
res |= (1 << i);
u = ch[u][b ^ 1];
} else u = ch[u][b];
}
return res;
}贪心正确性:异或值的高位优先,能取 1 就取 1(高位 1 比后面全 1 都大)。
AC 自动机(Aho-Corasick)
Trie + KMP 的 fail 指针——在文本中同时查找多个模式串。
结构:
1. 所有模式串建成 Trie
2. 每个节点加 fail 指针:指向"当前串的最长真后缀"对应的节点
(和 KMP 的 π 数组完全对应)
3. 匹配时沿 Trie 走,失配就跳 failstruct AC {
static const int N = 1e6 + 5, C = 26;
int ch[N][C], fail[N], cnt[N], tot = 0;
void insert(const string& s) {
int u = 0;
for (char c : s) { int k = c - 'a';
if (!ch[u][k]) ch[u][k] = ++tot;
u = ch[u][k]; }
cnt[u]++;
}
void build() {
queue<int> q;
for (int k = 0; k < C; k++)
if (ch[0][k]) q.push(ch[0][k]);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int k = 0; k < C; k++) {
int v = ch[u][k];
if (v) {
fail[v] = ch[fail[u]][k]; // 关键递推
q.push(v);
} else {
ch[u][k] = ch[fail[u]][k]; // 补全转移(优化,省去跳 fail)
}
}
}
}
int query(const string& T) {
int u = 0, ans = 0;
for (char c : T) {
u = ch[u][c - 'a']; // 因为补全了,直接走
for (int t = u; t && cnt[t] != -1; t = fail[t]) {
ans += cnt[t];
cnt[t] = -1; // 只计一次(可按需去掉)
}
}
return ans;
}
};复杂度:建树,匹配。
两个关键点:
fail[v] = ch[fail[u]][k]:BFS 保证fail[u]已算好(层数更浅)- 补全不存在的转移为
ch[fail[u]][k]:这样匹配时不用 while 跳 fail,直接一步走,快很多(以空间换时间)
应用:敏感词过滤、多模式匹配、结合 DP 做"不含某些串的字符串计数"。
回文
中心扩展法
// 以 i 为中心(奇数长度)和 i, i+1 之间(偶数长度)扩展
int expand(const string& s, int l, int r) {
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
return r - l - 1;
}
int longestPalindrome(const string& s) {
int best = 0;
for (int i = 0; i < (int)s.size(); i++) {
best = max(best, expand(s, i, i));
best = max(best, expand(s, i, i + 1));
}
return best;
},够用( 时)。
Manacher 算法
求每个位置为中心的最长回文半径。
// d1[i] = 以 i 为中心的奇数长度回文半径(含中心)
vector<int> manacher_odd(const string& s) {
int n = s.size();
vector<int> d1(n);
int l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); // 利用对称点
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
d1[i] = k;
if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
}
return d1;
}核心技巧:维护当前最右的回文区间,若 在其中,利用它关于中心 的对称点 的已知值作为初始值(mirroring),避免重复比较。
为什么是:r 单调递增,每步的 while 循环要么推进 r(总共 次),要么不推进。
偶数长度:先做一次字符间插入分隔符(如 #)的转换,abc → #a#b#c#,统一成奇数。
后缀数组(Suffix Array)
把字符串所有后缀按字典序排序,得到排名数组 sa。
s = "banana"
后缀:
"banana" sa[0] = 5 "a"
"anana" sa[1] = 3 "ana"
"nana" sa[2] = 1 "anana"
"ana" sa[3] = 0 "banana"
"na" sa[4] = 4 "na"
"a" sa[5] = 2 "nana"LCP 数组:lcp[i] = sa[i] 和 sa[i-1] 对应后缀的最长公共前缀。
构造(倍增法)
第 k 轮:按长度为 2^k 的子串排序
利用第 k-1 轮的排名,把 2^k 的子串看成两个 2^(k-1) 的排名对 → 基数排序 O(n)
共 log n 轮 → O(n log n)应用:
- 最长公共子串(两串拼接后求相邻后缀的 LCP 最大值)
- 最长重复子串(
lcp数组的最大值) - 不同子串个数()
- 模式匹配(二分 + LCP)
实现较复杂( 倍增 + 基数排序约 60 行),实际竞赛里常用后缀自动机替代。
后缀自动机(SAM)
用 的空间表示字符串的所有子串,是一个最小的 DFA。
- 状态数,转移数
- 构造,在线算法(逐字符添加)
- 从根出发的任意路径对应一个子串
应用:
- 不同子串个数
- 最长公共子串
- 子串出现次数
- 字典序第 k 小子串
比后缀数组更强大但更难理解。入门建议先学后缀数组。
常见坑
- KMP 的
pi数组定义:是"最长相等真前后缀长度",不是"最长前缀" - KMP 匹配后
j = pi[j-1]:忘了这步就找不到重叠的匹配 - Trie 的空间估算:
N = 总字符数,别开小了 - AC 自动机的
ch[u][k] = ch[fail[u]][k]补全:不加会 TLE(每步都要跳 fail) - AC 自动机统计时重复计数:一个模式串出现在多个位置,或者沿 fail 链会重复。按需去重
- 字符串哈希的碰撞:线上系统用哈希要先考虑攻击;竞赛里可能被卡
- Manacher 的偶数长度:要么做两次,要么插入分隔符
- 后缀数组的下标:
sa[i]是"排名第 i 的后缀的起始位置",rank[i]是"从 i 开始的后缀的排名"。两个数组容易搞混 - 字符集不是小写字母:用
map<char,int>或扩大C;但要注意空间 - 中文/UTF-8:
string按字节索引会切断多字节字符。要先解码成wchar_t或用专门的库