前言
2026 ICPC 训练题单，字符串题，主要涉及 回文串、KMP、字典树。
CF126B
题面
给定一个字符串 \(s\)，求一个字符串 \(t\)，满足：
- \(t\) 在 \(s\) 中出现至少 \(3\) 次；
- \(t\) 为 \(s\) 的前缀和后缀。
若不存在 \(t\)， 则输出 Just a legend。
其中 \(|s| \leq 10^6\)
思路
思路 1
该做法为我初想法。 对 \(s\) 正反求两次 KMP，遍历每个位置，判断其所在 border 是否同时为反向 border。
思路 2
对 \(s\) 求 KMP，然后通过 j = nxt[j]-1 向前跳 border 链，通过桶记录是否存在即可。
思路 3
考虑思路 2 向前跳 border 链的过程，发现，只要第一步跳到的位置 \(nxt[i] \neq 0\)，即存在 border 链，显然后续跳链一定不优。
实现
#include using namespace std;const int N = 1e6+5;string s;
int n, nxt[N], b[N];int main() {cin >> s;n = s.length();for(int i = 1, j = 0; i < n; i ++) {j = nxt[i-1];while(j && s[i] != s[j]) j = nxt[j-1];j += (s[i] == s[j]);++ b[nxt[i] = j];}if(b[nxt[n-1]] >= 2 && nxt[n-1] != 0) {cout << s.substr(0, nxt[n-1]) << "\n";}else if(nxt[nxt[n-1]-1] != 0) {cout << s.substr(0, nxt[nxt[n-1]-1]) << "\n";}else cout << "Just a legend\n";return 0;
}
CF471D
题面
给定两个数组 \(a_n, b_w\)，求存在多少个位置 \(p\) 满足：
其中 \(1 \leq n, w \leq 2 \times 10^5\)
思路
差分后即可转化为普通 KMP
实现
#include using namespace std;const int N = 4e5+5;
const int inf = 1e9+5;int n, w, a[N], nxt[N], u, v, ans;int main() {cin >> n >> w;for(int i = 0; i < n; i ++) {cin >> u;if(i != 0) {a[i+w-1] = u - v;}v = u;}for(int i = 0; i < w; i ++) {cin >> u;if(i != 0) {a[i-1] = u - v;}v = u;}a[w-1] = inf;if(w == 1) {cout << n << "\n";return 0;}if(n < w) {cout << "0\n";return 0;}for(int i = 1, j = 0; i < n+w-1; i ++) {j = nxt[i-1];while(j && a[i] != a[j]) j = nxt[j-1];j += (a[i] == a[j]);nxt[i] = j;if(nxt[i] == w-1) {++ans;}}cout << ans << "\n";return 0;
}
CF1705D
题面
多测
给定两个长度为 \(n\) 的 01 串 \(s, t\)。
你可以对 \(s\) 进行若干次操作(可以为 \(0\))：
- 选择一个 \(2 \leq i \leq n-1\)，满足 \(s_{i-1} \neq s_{i+1}\);
- 反转 \(s_i\);
最小化使得 \(s\) 变为 \(t\) 的操作次数，若无法操作使得 \(s\) 变为 \(t\)，输出 -1
\(1 \leq n \leq 2\times10^5\)
思路
对 \(s_i\) 进行差分，发现操作不会改变差分中 \(0, 1, -1\) 的数量与相对顺序，且一次操作会将 \(1\) 或 \(-1\) 移动一格。 判断 \(1, -1\) 的数量与位移即可。
异或差分也行。
实现
#include #define ll long longusing namespace std;const int N = 2e5+5;int tt;
int n;
int s[N], t[N];
ll ans;
string str;
char st, ed;void solve() {cin >> n;cin >> str;ans = 0;st = str[0];ed = str[n-1];for(int i = 1; i < n; i ++) {s[i] = str[i] - str[i-1];}cin >> str;for(int i = 1; i < n; i ++) {t[i] = str[i] - str[i-1];}if(str[0] != st || str[n-1] != ed) {cout << "-1\n";return;}for(int i = 1, j = 1; i < n || j < n; i ++, j ++) {while(s[i] == 0 && i < n) i ++;while(t[j] == 0 && j < n) j ++;if(i == n || j == n) {if(i != j) {cout << "-1\n";}else {cout << ans << "\n";}return;}if(s[i] != t[j]) {cout << "-1\n";return;}ans += abs(i-j);}cout << ans << "\n";
}int main() {cin >> tt;while(tt --) solve();
}
CF835D
题面
若一个字符串为回文串，则其为 \(1\)-回文串；
若一个字符串 \(t_{n}\) 满足：
- \(t[1, \dots, \lfloor n/2 \rfloor] = t[ \lfloor n+3/2 \rfloor, \dots, n]\)；
- \(t[1, \dots, \lfloor n/2 \rfloor]\) 为 \(k-1\)-回文串。
则 \(t\) 为 \(k\)-回文串。
给定一个字符串 \(s\)，对于 \(i \in \{1, \dots, |s|\}\)，输出其 \(i\)-回文子串的个数。
其中 \(|s| \leq 5000\)
题解
本题我没有想出思路，看的题解的思路。
设 \(d[i][j]\) 表示 \(t[i, \dots, j]\) 的最大回文阶数。
然后我们可以使用朴素的 \(O(n^2)\) 判断回文子串的方法：枚举中心点并向外扩张，来进行 \(d[i][j]\) 的转移。
实现
/*
n <= 5000 可以考虑朴素的回文串算法
用 d[l][r] 记录 s[l...r] 的最高回文等级，所以 d[l][r] = d[l][mid] + 1
*/
#include using namespace std;const int N = 5005;int d[N][N], n, ans[N];
string s;int main() {cin >> s;n = s.length();for(int i = 0; i < n; i ++) {d[i][i] = 1;for(int k = 0;; k ++) {if(i+k >= n || i-k <0) break;if(s[i+k] != s[i-k]) break;ans[d[i-k][i+k] = d[i-k][i-1] + 1] ++;}for(int k = 0;; k ++) {if(i+k >= n || i-k-1 < 0) break;if(s[i+k] != s[i-k-1]) break;ans[d[i-k-1][i+k] = d[i-k-1][i-1] + 1] ++;}}for(int i = n; i > 1; i --) {ans[i-1] += ans[i];}for(int i = 1; i <= n; i ++) {cout << ans[i] << " ";}cout << "\n";return 0;
}
CF1902E
题面
对于两个字符串 \(a, b\)，定义 \(C(a, b)\) 如下：
- 若 \(a\) 为空，则 \(C(a, b) = b\)；
- 若 \(b\) 为空，则 \(C(a, b) = a\)；
- 若 \(a_{|a|} = b_{1}\)，则 \(C(a, b) = C(a[1, \dots, |a|-1], b[2, \dots, |b|])\)；
- 否则 \(C(a, b) = a + b\)。
给定 \(n\) 个字符串 \(s_1, \dots, s_n\)，求 \(\sum_{i=1}^{n}\sum_{j=1}^{n} |C(s_i, s_j)|\)。
其中 \(1 \leq n, \sum|s_i|, \leq 10^6\)
思路
正难则反，我们考虑求 \(|s_i|+|s_j|-|C(s_i, s_j)|\)。
显然，这为 \(LCP(\text{reverse}(s_i), s_j)\)，我们可以通过将 \(s_i\) 反插入 Trie 中，再正向查找 \(s_j\)。
这里正反可以互换，为方便实现采用正插反查。
实现
#include
#include #define ll long longusing namespace std;const int N = 1e6+5;int n;
ll ans;
string s[N];
int ch[N][26], cnt, siz[N];void insert(string str, int len) {int now = 0, c;for(int i = 0; i < len; i ++) {c = str[i] - 'a';if(!ch[now][c]) {ch[now][c] = ++cnt;}now = ch[now][c];++siz[now];}
}
void query(string str, int len) {int now = 0, c;for(int i = 0; i < len; i ++) {c = str[i] - 'a';if(!ch[now][c]) return;now = ch[now][c];ans -= 2*siz[now];}
}int main() {cin >> n;for(int i = 1; i <= n; i ++) {cin >> s[i];insert(s[i], s[i].length());ans += s[i].length();}ans *= 2*n;for(int i = 1; i <= n; i ++) {reverse(s[i].begin(), s[i].end());query(s[i], s[i].length());}cout << ans << "\n";return 0;
}
CF432D
题面
给定一个字符串 \(s\)，求其每一个 border 在其中出现的次数。
其中 \(|s| <= 10^5\)
思路
我 border 的 border 也是我的 border。
所以我们直接跳 border 链，后缀和求解。
实现
#include
#include using namespace std;const int N = 1e5+5;int n;
string s;
int nxt[N], siz[N];
stack ans;int main() {cin >> s;n = s.length();siz[0] = 1;for(int i = 1, j = 0; i < n; i ++) {siz[i] = 1;j = nxt[i-1];while(j && s[j] != s[i]) j = nxt[j-1];j += (s[i] == s[j]);nxt[i] = j;}for(int i = n-1; i > 0; i --) {if(nxt[i]>0) siz[nxt[i]-1] += siz[i];}int j = n-1;while(j>=0) {ans.push(j);j = nxt[j]-1;}cout << ans.size() << "\n";while(!ans.empty()) {cout << ans.top()+1 << " " << siz[ans.top()] << "\n";ans.pop();}return 0;
}
CF1200E*
题面
定义 \(\text{merge}(a, b) = a + b[len+1, \dots, |b|]\)，
其中 \(len = \text{maxarg}_{l} a[|a|-l+1, \dots, |a|] = b[1, \dots, len]\)。
给定 \(n\) 个字符串 \(s_1, \dots, s_n\)。
记 \(t_1 = s_1, t_i = \text{merge}(t_{i-1}, s_i)\)，求 \(t_n\)。
其中 \(\sum |s_i| \leq 10^6\)
题解
朴素的做法是对 \(s_i + \# +t_{i-1}\) 做一次 KMP 以求解 \(len\)。
但是这样复杂度是 \(O(n \times \sum|s_i|)\)。
注意到 \(len \leq |s_i|\)，所以我们只需要 KMP 判断 \(t_{i-1}\) 的后 \(|s_i|\) 个字符，所以复杂度变为 \(O(\sum|s_i|)\)。
实现
#include using namespace std;const int N = 2e6+5;int nxt[N];int kmp(const string& A, const string& B) {string s = B + "#" + (A.length() > B.length() ? A.substr( A.length()-B.length()) : A);int len = s.length();int j = 0;for(int i = 1; i < len; i ++) {j = nxt[i-1];while(j && s[i] != s[j]) j = nxt[j-1];j += (s[i] == s[j]);nxt[i] = j;}return j;
}int n;
string A, B;int main() {cin >> n;for(int i = 1; i <= n; i ++) {cin >> B;A += B.substr(kmp(A, B));}cout << A << "\n";return 0;
}
CF25E
题面
给定三个字符串 \(s_1, s_2, s_3\)
求最短的字符串 \(t\) 的长度，满足 \(s_1, s_2, s_3\) 均为 \(t\) 的子串。
其中 \(|s_i| \leq 10^5\)
思路
和上一题类似，我们考虑按照顺序合并 \(s_i\)。
首先对 \(s_i\) 进行全排列，然后按次合并：
- 若 \(a\) 为 \(b\) 的子串，返回 \(b\);
- 若 \(b\) 为 \(a\) 的子串，返回 \(a\);
- 返回和上一题一样的 \(\text{merge}(a, b)\)。
复杂度为 \(O(n)\)，常数大约有 \(30\)。
实现
#include using namespace std;const int N = 3e5+50;int ans = 1e9+5, nxt[N];
string s[3];int kmp(const string& A, const string& B) {string s = B + '#' + A;int len = s.length(), j = 0;for(int i = 1; i < len; i ++) {j = nxt[i-1];while(j && s[i] != s[j]) j = nxt[j-1];if(s[i] == s[j]) {if(j == B.length()-1) return -1;j ++;}nxt[i] = j;}return j;
}void check(int a, int b, int c) {string A = s[a];int l;l = kmp(A, s[b]);if(l != -1) A += s[b].substr(l);l = kmp(A, s[c]);if(l != -1) A += s[c].substr(l);ans = min(ans, (int)A.length());
}int main() {cin >> s[0] >> s[1] >> s[2];check(0, 1, 2);check(0, 2, 1);check(1, 0, 2);check(1, 2, 0);check(2, 0, 1);check(2, 1, 0);cout << ans << "\n";return 0;
}
CF1537E2
题面
给定两个整数 \(n, k\)，与一个长度为 \(n\) 的字符串 \(s\)。
你可以对 \(s\) 进行若干次以下两种操作：
- 删除 \(s\) 的最后一个元素；
- 令 \(s \gets s + s\)。
求最终的长度为 \(k\) 的字典序最小的字符串 \(s\)。
思路
思路 1
显然，答案一定是 \(s\) 的某个前缀 \(p\) 的无限重复。
那么若 \(p\) 为答案，则一定有 \(p <> s[|p|+1, \dots, 2|p|]\)。
首先对 \(s+s\) 进行 KMP，
然后我们枚举 \(p\)，然后通过二分，找出 \(p\) 与 \(s[|p|+1, \dots, 2|p|]\) 的 LCP，可以通过比较 \(p[|LCP|]\) 与 \(s[|p|+|LCP|]\) 即可。
思路 2
我们通过双指针实现。
\(i\) 代表匹配的前缀 \(p\)， \(j\) 代表被匹配的 \(s[|p|+1, \dots, 2|p|]\)，显然：
- \(s[i] = s[j]\)，令二者加一；
- \(s[i] > s[j]\)，令 \(i \gets 1\)，开始重新匹配；
- \(s[i] < s[j]\)，这时 \(p <> s[|p|, \dots, 2|p|]\)，\(|p| = j\)。
实现
思路 1 实现详见 CF1537E2。
#include using namespace std;int n, k;
string s;int main() {cin >> n >> k >> s;int i = 0, j = 1, ans = 0;while(j < n) {if(s[i] == s[j]) {++i;++j;}else if(s[i] > s[j]) {ans = j;i = 0;++j;}else break;}for(i = 0; i < k; i ++) {cout << s[i%(ans+1)];}cout << "\n";return 0;
}CF808G
题面
给定两个字符串 \(s, t\)。
其中 \(s\) 仅包含小写字母和 ?，\(t\) 仅包含小写字母。
你需要将 \(s\) 中的所有 ?，替换成小写字母，并最大化 \(s\) 中 \(t\) 作为子串出现的次数。
其中 \(|s|, |t| \leq 10^5\)， \(|s|\cdot|t| \leq 10^7\)
思路
数据范围提示我们，这题是 \(O(|s|\cdot|t|)\) 的。
首先，我们可以枚举，以求解 \(s\) 中可以安放 \(t\) 的位置。定义 \(\text{ok}[i]=1\) 代表 \(s[i, \dots, i+|t|-1] = t\)。
然后考虑 DP。
若 \(\text{ok}[i] = 1\)，那么显然有 \(\displaystyle dp[i] = \max \left ( \max_{j \leq i - |t|} (dp[j]) , \max_{j = i - |t| + u, u \in \text{border}(t)} (dp[j])\right) + 1\)。
前者可以通过前缀最大值求解，后者通过 KMP 求解 border 链即可。
实现
#include
#include using namespace std;const int N = 1e5+5;int n, m;
string s, t;
int dp[N], mx[N], nxt[N];
bool ok[N];
vector border;void get_ok() {for(int i = 0; i < n; i ++) {for(int j = 0; j < m; j ++) {if(s[i+j] != t[j] && s[i+j] != '?') break;if(j == m-1) ok[i] = 1;}}
}void kmp() {for(int i = 1, j = 0; i < m; i ++) {j = nxt[i-1];while(j && t[i] != t[j]) j = nxt[j-1];j += (t[i] == t[j]);nxt[i] = j;}for(int j = m-1; j>0;) {border.push_back(m-nxt[j]);j = nxt[j]-1;}
}int main() {cin >> s >> t;n = s.length();m = t.length();if(m > n) {cout << "0\n";return 0;}kmp();get_ok();for(int i = 0; i < n; i ++) {if(ok[i]) {if(i-m >= 0) dp[i] = mx[i-m];for(auto u: border) {if(i-u >= 0) dp[i] = max(dp[i], dp[i-u]);}++ dp[i];}mx[i] = max(mx[i-1], dp[i]);}cout << mx[n-1] << "\n";return 0;
}
CF149E
题面
给定一个字符串 \(s\) 与 \(m\) 个字符串 \(\{t_1, \dots, t_m\}\)。
你需要计算满足以下条件的 \(t_i\) 的数量：
- 存在 \(a \leq b \lt c \leq d\)，使得 \(s[a, \dots, b] + s[c, \dots, d] = t\)。
其中 \(|s| \leq 10^5, m \leq 100, |s_i| \leq 1000\)
思路
对于一个 \(t_i\) 我们枚举其长度为 \(j\) 的前缀第一次在 \(s\) 中出现时最后一个字符的位置 \(pre[i][j]\)，
与其长度为 \(k\) 的后缀最后一次在 \(s\) 中出现时第一个字符距离 \(s\) 末尾的距离 \(suf[i][j]\)。
可以通过 KMP 在 \(O(m \dots |s|)\) 的时间求解。
然后我们只需要比较 \(pre[i][j] + suf[i][|t_i|-j]\) 与 \(|s|\) 即可。
枚举一下，复杂度 \(O(m \dots |t_i|)\)。
需要注意的是 \(s[a, \dots, b]\) 与 \(s[c, \dots , d]\) 均非空。
实现
#include
#include
#include using namespace std;const int N = 1e5+1e3+50;int n, m, ans, nxt[N];
string s, t, p, sp;
vector pos, sop;void kmp(const string& str, int len, int l, bool tp) {int base = 0;for(int i = 1, j = 0; i < len; i ++) {j = nxt[i-1];while(j && str[i] != str[j]) j = nxt[j-1];j += (str[i] == str[j]);nxt[i] = j;if(i > l && nxt[i] > base) {if(tp) pos.push_back(i-l);else sop.push_back(i-l);++ base;}}
}void solve() {pos.clear();sop.clear();pos.push_back(0);sop.push_back(0);cin >> t;p = t + "#" + s;int l = t.length();kmp(p, p.length(), l, 1);reverse(t.begin(), t.end());p = t + "#" + sp;kmp(p, p.length(), l, 0);for(int i = 1; i < pos.size(); i ++) {if(l-i < sop.size() && l-i > 0) {if(pos[i]+sop[l-i] <= s.length()) {++ans;return;}}}
}int main() {cin >> s >> m;n = s.length();sp = s;reverse(sp.begin(), sp.end());while(m --) solve();cout << ans << "\n";return 0;
}
CF1202E
题面
定义 \(f(s, t)\) 为 \(t\) 作为子串在 \(s\) 中出现的次数。
给定一个字符串 \(t\) 与 \(n\) 个字符串 \(\{s_1, \dots, s_n\}\)。
求 \(\sum_i \sum_j f(t, s_i + s_j)\)。
其中 \(|t|, \sum|s_i| \leq 2 \times 10^5\)。
思路
定义 \(\text{end}[k]\) 代表 \(s_i\) 在 \(t\) 中出现，且以 \(k\) 为结尾的次数； 定义 \(\text{start}[k]\) 代表 \(s_i\) 在 \(t\) 中出现，且以 \(k\) 为开头的次数。
所以答案为 \(\sum_i \text{end}[i] \times \text{start}[i+1]\)。
通过 AC自动机 正序可以求出 \(\text{end}[]\)，再对于反串建立 AC自动机即可。
实现
#include
#include
#include using namespace std;const int N = 1e5+1e3+50;int n, m, ans, nxt[N];
string s, t, p, sp;
vector pos, sop;void kmp(const string& str, int len, int l, bool tp) {int base = 0;for(int i = 1, j = 0; i < len; i ++) {j = nxt[i-1];while(j && str[i] != str[j]) j = nxt[j-1];j += (str[i] == str[j]);nxt[i] = j;if(i > l && nxt[i] > base) {if(tp) pos.push_back(i-l);else sop.push_back(i-l);++ base;}}
}void solve() {pos.clear();sop.clear();pos.push_back(0);sop.push_back(0);cin >> t;p = t + "#" + s;int l = t.length();kmp(p, p.length(), l, 1);reverse(t.begin(), t.end());p = t + "#" + sp;kmp(p, p.length(), l, 0);for(int i = 1; i < pos.size(); i ++) {if(l-i < sop.size() && l-i > 0) {if(pos[i]+sop[l-i] <= s.length()) {++ans;return;}}}
}int main() {cin >> s >> m;n = s.length();sp = s;reverse(sp.begin(), sp.end());while(m --) solve();cout << ans << "\n";return 0;
}