3889 字
19 分钟
字符串算法详解：从CSP-S到IOI
字符串算法详解：从CSP-S到IOI
字符串算法是信息学竞赛中的重要组成部分，从基础的模式匹配到高级的后缀结构，涵盖了广泛的应用场景。本文将系统地介绍从CSP-S到IOI级别的核心字符串算法。
1. 字符串基础操作
1.1 字符串表示与存储
在C++中，字符串有多种表示方式：
#include <iostream>#include <string>#include <cstring>using namespace std;
// 方式1：C风格字符串char s1[1005] = "hello";
// 方式2：C++ string类string s2 = "world";
// 方式3：字符数组（常用于OI）char s3[1005];scanf("%s", s3);1.2 常用操作
// 字符串长度int len1 = strlen(s1); // C风格int len2 = s2.length(); // string类
// 字符串比较if (strcmp(s1, s3) == 0) { /* 相等 */ }if (s2 == "world") { /* 相等 */ }
// 字符串拼接strcat(s1, s3); // C风格string s4 = s2 + "!"; // string类
// 子串提取string sub = s2.substr(0, 3); // "wor"2. 字符串哈希
字符串哈希是一种将字符串映射到数值的技术，可以快速比较字符串是否相同。
2.1 单哈希
原理：将字符串看作P进制数，对M取模得到哈希值。
const int P = 131; // 或 13331const int M = 1e9 + 7;
// 计算字符串哈希值unsigned long long getHash(string s) { unsigned long long hash = 0; for (char c : s) { hash = hash * P + c; } return hash;}
// 预处理前缀哈希（支持O(1)查询子串哈希）const int N = 1e5 + 5;unsigned long long h[N], p[N]; // h[i]为前i个字符的哈希，p[i]=P^i
void initHash(string s) { int n = s.length(); p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i-1] * P + s[i-1]; p[i] = p[i-1] * P; }}
// 获取子串[l, r]的哈希值（下标从1开始）unsigned long long getSubHash(int l, int r) { return h[r] - h[l-1] * p[r-l+1];}2.2 双哈希
为了降低哈希冲突概率，可以使用两个不同的模数：
const int P = 131;const int M1 = 1e9 + 7;const int M2 = 1e9 + 9;
struct HashPair { long long h1, h2; bool operator == (const HashPair& other) const { return h1 == other.h1 && h2 == other.h2; }};
HashPair h[N], p[N];
void initDoubleHash(string s) { int n = s.length(); p[0] = {1, 1}; for (int i = 1; i <= n; i++) { h[i].h1 = (h[i-1].h1 * P + s[i-1]) % M1; h[i].h2 = (h[i-1].h2 * P + s[i-1]) % M2; p[i].h1 = (p[i-1].h1 * P) % M1; p[i].h2 = (p[i-1].h2 * P) % M2; }}复杂度分析：
- 预处理：O(n)
- 查询子串哈希：O(1)
应用场景：
- 快速判断两个子串是否相同
- 最长公共子串问题
- 回文子串检测
3. KMP算法
KMP（Knuth-Morris-Pratt）算法是经典的字符串模式匹配算法，可以在O(n+m)时间内完成匹配。
3.1 原理
KMP的核心是next数组（也叫失配数组或前缀函数），next[i]表示模式串前i个字符的最长相等前后缀长度。
3.2 实现
const int N = 1e6 + 5;int nxt[N]; // next是关键字，用nxt代替
// 计算next数组void getNext(string p) { int m = p.length(); nxt[0] = 0; for (int i = 1, j = 0; i < m; i++) { while (j > 0 && p[i] != p[j]) { j = nxt[j-1]; } if (p[i] == p[j]) { j++; } nxt[i] = j; }}
// KMP匹配，返回所有匹配位置vector<int> KMP(string s, string p) { int n = s.length(), m = p.length(); vector<int> result; getNext(p);
for (int i = 0, j = 0; i < n; i++) { while (j > 0 && s[i] != p[j]) { j = nxt[j-1]; } if (s[i] == p[j]) { j++; } if (j == m) { result.push_back(i - m + 1); // 匹配位置 j = nxt[j-1]; // 继续寻找下一个匹配 } } return result;}3.3 优化版本
// 优化的next数组，避免重复比较void getNextOpt(string p) { int m = p.length(); nxt[0] = -1; for (int i = 0, j = -1; i < m; ) { if (j == -1 || p[i] == p[j]) { i++; j++; // 优化：如果下一个字符相同，直接跳过 nxt[i] = (p[i] != p[j]) ? j : nxt[j]; } else { j = nxt[j]; } }}复杂度分析：
- 时间复杂度：O(n + m)
- 空间复杂度：O(m)
应用场景：
- 文本编辑器的查找功能
- DNA序列匹配
- 数据压缩
4. 字典树 Trie
Trie树是一种用于快速检索字符串的树形数据结构。
4.1 基本结构
const int MAXN = 1e5 + 5;const int CHAR_SIZE = 26;
struct Trie { int ch[MAXN][CHAR_SIZE]; // 子节点 int cnt[MAXN]; // 以当前节点结尾的字符串个数 int idx; // 节点编号
Trie() { idx = 0; memset(ch, 0, sizeof(ch)); memset(cnt, 0, sizeof(cnt)); }
// 插入字符串 void insert(string s) { int p = 0; for (char c : s) { int u = c - 'a'; if (!ch[p][u]) ch[p][u] = ++idx; p = ch[p][u]; } cnt[p]++; }
// 查询字符串出现次数 int query(string s) { int p = 0; for (char c : s) { int u = c - 'a'; if (!ch[p][u]) return 0; p = ch[p][u]; } return cnt[p]; }
// 查询前缀出现次数 int queryPrefix(string s) { int p = 0, count = 0; for (char c : s) { int u = c - 'a'; if (!ch[p][u]) return count; p = ch[p][u]; count += cnt[p]; } return count; }};4.2 应用：最大异或对
利用Trie可以高效求解最大异或对问题：
struct BinaryTrie { int ch[MAXN * 31][2]; int idx;
void insert(int x) { int p = 0; for (int i = 30; i >= 0; i--) { int u = (x >> i) & 1; if (!ch[p][u]) ch[p][u] = ++idx; p = ch[p][u]; } }
int queryMax(int x) { int p = 0, res = 0; for (int i = 30; i >= 0; i--) { int u = (x >> i) & 1; // 尽量走相反的路径 if (ch[p][!u]) { p = ch[p][!u]; res |= (1 << i); } else { p = ch[p][u]; } } return res; }};复杂度分析：
- 插入：O(|S|)
- 查询：O(|S|)
- 空间：O(总字符数 × 字符集大小)
5. AC自动机
AC自动机（Aho-Corasick Automaton）是多模式串匹配算法，可以同时匹配多个模式串。
5.1 原理
AC自动机 = Trie + KMP的fail指针
5.2 实现
const int MAXN = 1e6 + 5;
struct ACAutomaton { int ch[MAXN][26]; int fail[MAXN]; // fail指针 int cnt[MAXN]; // 标记节点 int idx;
void init() { idx = 0; memset(ch, 0, sizeof(ch)); memset(cnt, 0, sizeof(cnt)); memset(fail, 0, sizeof(fail)); }
// 插入模式串 void insert(string s) { int p = 0; for (char c : s) { int u = c - 'a'; if (!ch[p][u]) ch[p][u] = ++idx; p = ch[p][u]; } cnt[p]++; }
// 构建fail指针（BFS） void build() { queue<int> q; for (int i = 0; i < 26; i++) { if (ch[0][i]) q.push(ch[0][i]); }
while (!q.empty()) { int p = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (ch[p][i]) { // 找到fail指针 fail[ch[p][i]] = ch[fail[p]][i]; q.push(ch[p][i]); } else { // 路径压缩优化 ch[p][i] = ch[fail[p]][i]; } } } }
// 在文本串中匹配 int query(string s) { int p = 0, res = 0; for (char c : s) { int u = c - 'a'; p = ch[p][u]; // 路径压缩后直接转移
// 统计匹配 for (int t = p; t && cnt[t] != -1; t = fail[t]) { res += cnt[t]; cnt[t] = -1; // 避免重复计数 } } return res; }};复杂度分析：
- 构建：O(总字符数 × 字符集大小)
- 匹配：O(|文本| + 匹配次数)
应用场景：
- 敏感词过滤
- 病毒特征码匹配
- 多模式串检索
6. 后缀数组 SA
后缀数组是一种强大的字符串数据结构，可以解决很多复杂的字符串问题。
6.1 基本概念
- sa[i]：排名第i的后缀的起始位置
- rk[i]：起始位置为i的后缀的排名
- height[i]：排名相邻的两个后缀的最长公共前缀（LCP）
6.2 倍增算法
const int MAXN = 1e6 + 5;
struct SuffixArray { int sa[MAXN], rk[MAXN], tmp[MAXN]; int height[MAXN]; int n; string s;
// O(n log n) 构建后缀数组 void buildSA() { n = s.length(); // 初始化 for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s[i]; }
// 倍增 for (int k = 1; k < n; k *= 2) { // 基数排序 auto cmp = [&](int i, int j) { if (rk[i] != rk[j]) return rk[i] < rk[j]; int ri = (i + k < n) ? rk[i + k] : -1; int rj = (j + k < n) ? rk[j + k] : -1; return ri < rj; }; sort(sa, sa + n, cmp);
// 更新rk tmp[sa[0]] = 0; for (int i = 1; i < n; i++) { tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0); } memcpy(rk, tmp, sizeof(int) * n); } }
// 构建height数组 void buildHeight() { int k = 0; for (int i = 0; i < n; i++) { if (rk[i] == 0) continue; if (k) k--; int j = sa[rk[i] - 1]; while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } }
// 初始化 void init(string str) { s = str; buildSA(); buildHeight(); }};6.3 应用：最长重复子串
// 找最长重复子串（出现至少两次）string longestRepeatedSubstring(string s) { SuffixArray sa; sa.init(s);
int maxLen = 0, pos = 0; for (int i = 1; i < sa.n; i++) { if (sa.height[i] > maxLen) { maxLen = sa.height[i]; pos = sa.sa[i]; } }
return s.substr(pos, maxLen);}复杂度分析：
- 倍增算法：O(n log n)
- DC3算法：O(n)
- height数组：O(n)
7. Manacher算法
Manacher算法用于在O(n)时间内求解最长回文子串问题。
7.1 原理
通过添加分隔符将问题统一为奇数长度回文，利用回文的对称性减少比较次数。
7.2 实现
string preprocess(string s) { string t = "^#"; for (char c : s) { t += c; t += '#'; } t += '$'; return t;}
// 返回最长回文子串string manacher(string s) { string t = preprocess(s); int n = t.length(); vector<int> p(n, 0); // p[i]为以i为中心的回文半径
int center = 0, right = 0; // 当前最右回文的中心和右边界 int maxLen = 0, maxCenter = 0;
for (int i = 1; i < n - 1; i++) { // 利用对称性 int mirror = 2 * center - i; if (i < right) { p[i] = min(right - i, p[mirror]); }
// 尝试扩展 while (t[i + p[i] + 1] == t[i - p[i] - 1]) { p[i]++; }
// 更新右边界 if (i + p[i] > right) { center = i; right = i + p[i]; }
// 记录最长回文 if (p[i] > maxLen) { maxLen = p[i]; maxCenter = i; } }
// 提取原字符串中的回文 int start = (maxCenter - maxLen) / 2; return s.substr(start, maxLen);}复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
8. 字符串DP问题
8.1 最长公共子序列（LCS）
int LCS(string s1, string s2) { int n = s1.length(), m = s2.length(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } }
return dp[n][m];}8.2 编辑距离
int editDistance(string s1, string s2) { int n = s1.length(), m = s2.length(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 初始化 for (int i = 0; i <= n; i++) dp[i][0] = i; for (int j = 0; j <= m; j++) dp[0][j] = j;
// DP转移 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min({ dp[i-1][j] + 1, // 删除 dp[i][j-1] + 1, // 插入 dp[i-1][j-1] + 1 // 替换 }); } } }
return dp[n][m];}8.3 回文子串个数
int countPalindromes(string s) { int n = s.length(); vector<vector<bool>> dp(n, vector<bool>(n, false)); int count = 0;
// 长度为1的回文 for (int i = 0; i < n; i++) { dp[i][i] = true; count++; }
// 长度为2的回文 for (int i = 0; i < n - 1; i++) { if (s[i] == s[i+1]) { dp[i][i+1] = true; count++; } }
// 长度>=3的回文 for (int len = 3; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s[i] == s[j] && dp[i+1][j-1]) { dp[i][j] = true; count++; } } }
return count;}9. 后缀自动机 SAM（IOI难度）
后缀自动机是最强大的字符串数据结构之一，可以在线性时间内处理几乎所有字符串问题。
9.1 基本概念
SAM是一个能识别一个字符串所有后缀的最小DFA（确定有限状态自动机）。
9.2 核心实现
const int MAXN = 2e6 + 5;
struct SAM { int ch[MAXN][26]; // 转移 int link[MAXN]; // 后缀链接 int len[MAXN]; // 最长字符串长度 int cnt[MAXN]; // endpos集合大小 int last, idx;
void init() { idx = last = 0; memset(ch, 0, sizeof(ch)); memset(link, -1, sizeof(link)); memset(len, 0, sizeof(len)); memset(cnt, 0, sizeof(cnt)); }
// 添加字符 void extend(int c) { int cur = ++idx; len[cur] = len[last] + 1; cnt[cur] = 1;
int p = last; while (p != -1 && !ch[p][c]) { ch[p][c] = cur; p = link[p]; }
if (p == -1) { link[cur] = 0; } else { int q = ch[p][c]; if (len[p] + 1 == len[q]) { link[cur] = q; } else { int clone = ++idx; len[clone] = len[p] + 1; memcpy(ch[clone], ch[q], sizeof(ch[q])); link[clone] = link[q];
while (p != -1 && ch[p][c] == q) { ch[p][c] = clone; p = link[p]; }
link[q] = link[cur] = clone; } }
last = cur; }
// 构建SAM void build(string s) { init(); for (char c : s) { extend(c - 'a'); } }
// 统计endpos大小（需要拓扑排序） void calcEndpos() { vector<int> bucket[MAXN]; for (int i = 1; i <= idx; i++) { bucket[len[i]].push_back(i); }
for (int i = idx; i >= 1; i--) { for (int u : bucket[i]) { if (link[u] != -1) { cnt[link[u]] += cnt[u]; } } } }
// 查询子串出现次数 int queryCount(string t) { int p = 0; for (char c : t) { int u = c - 'a'; if (!ch[p][u]) return 0; p = ch[p][u]; } return cnt[p]; }
// 计算不同子串个数 long long countDistinct() { long long ans = 0; for (int i = 1; i <= idx; i++) { ans += len[i] - len[link[i]]; } return ans; }};9.3 应用示例
// 最长公共子串（多个字符串）int longestCommonSubstring(vector<string>& strs) { if (strs.empty()) return 0;
SAM sam; sam.build(strs[0]);
int ans = 0; for (int i = 1; i < strs.size(); i++) { int p = 0, len = 0, maxLen = 0; for (char c : strs[i]) { int u = c - 'a'; while (p && !sam.ch[p][u]) { p = sam.link[p]; len = sam.len[p]; } if (sam.ch[p][u]) { p = sam.ch[p][u]; len++; } maxLen = max(maxLen, len); } ans = (i == 1) ? maxLen : min(ans, maxLen); }
return ans;}复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n × 字符集大小)
- 节点数：≤ 2n - 1
- 边数：≤ 3n - 4
10. 经典竞赛题目
10.1 基础题目（CSP-S / 省选）
-
P3375 【模板】KMP字符串匹配
- 难度：普及+/提高
- 考点：KMP算法
-
P3808 【模板】AC自动机（简单版）
- 难度：提高+/省选-
- 考点：AC自动机
-
P3796 【模板】AC自动机（加强版）
- 难度：省选/NOI-
- 考点：AC自动机 + 统计
-
P4551 最长异或路径
- 难度：省选/NOI-
- 考点：字典树 + 异或
10.2 进阶题目（NOI / CTSC）
-
P3804 【模板】后缀自动机
- 难度：NOI/NOI+
- 考点：SAM基础应用
-
P2408 不同子串个数
- 难度：NOI-
- 考点：SAM / 后缀数组
-
P3181 [HAOI2016]找相同字符
- 难度：NOI/NOI+
- 考点：SAM / 后缀数组 + LCP
10.3 高级题目（IOI / WC）
-
P6139 【模板】广义后缀自动机
- 难度：NOI+/WC
- 考点：广义SAM
-
P4094 [HEOI2016/TJOI2016]字符串
- 难度：NOI+
- 考点：后缀数组 + 二分 + 线段树
-
P5546 [POI2000]公共串
- 难度：NOI+/WC
- 考点：SAM + 动态规划
10.4 解题技巧
-
选择合适的算法：
- 单模式匹配 → KMP
- 多模式匹配 → AC自动机
- 子串问题 → 哈希 / SAM
- 后缀问题 → 后缀数组 / SAM
-
常见优化技巧：
- 字符串哈希：降低常数，快速比较
- 路径压缩：AC自动机优化转移
- 拓扑排序：SAM统计endpos
- 倍增/ST表：RMQ优化LCP查询
-
调试技巧：
- 小数据手模
- 输出中间状态
- 对拍验证正确性
- 特殊数据测试（全相同、全不同）
总结
字符串算法是算法竞赛的重要组成部分，掌握以下要点：
-
基础算法（CSP-S必备）：
- 字符串哈希
- KMP算法
- 字典树Trie
-
进阶算法（省选/NOI）：
- AC自动机
- Manacher算法
- 后缀数组
-
高级算法（NOI+/IOI）：
- 后缀自动机SAM
- 广义SAM
- 回文自动机
建议学习路径：
- 先掌握基础的字符串哈希和KMP
- 熟练运用Trie和AC自动机
- 理解后缀数组的构造和应用
- 最后挑战SAM及其高级应用
每个算法都要：
- 理解原理和证明
- 手写代码实现
- 刷相关题目巩固
- 总结常见套路
字符串算法看似复杂，但只要循序渐进、多加练习，一定能够掌握！加油！
参考资料
- 《算法竞赛进阶指南》- 李煜东
- 《算法导论》- CLRS
- OI Wiki - 字符串专题
- Codeforces 字符串专题
- 洛谷题单 - 字符串算法
本文涵盖了从CSP-S到IOI级别的核心字符串算法，希望对你的学习有所帮助！
字符串算法详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-string/