Codeforces Round 1087 (Div. 2)——CF-2209-E. A Trivial String Problem(如何计算最短 border?)(字符串相关题目,我们采用 0-based,其他题目一般采用 1-based) · znzryb
## 题目大意
**题目描述**
定义函数 $f(t)$ 为:将字符串 $t$ 划分为若干部分的最大数量,满足每个部分都是 $t$ 的**非空前缀**。
There exist $k$ strings $p_1,p_2,\ldots,p_k$, **which are prefixes of** $t$, such that $t=p_1+p_2+\ldots+p_k$. Here $+$ denotes the string concatenation.
换句话说,$f(t)$ 是满足以下条件的最大正整数 $k$:**存在** $k$ **个字符串** $p_1, p_2, \dots, p_k$**,它们都是** $t$ **的前缀**,且 $t = p_1 + p_2 + \dots + p_k$($+$ 表示字符串拼接)。
给定一个长度为 $n$ 的小写英文字符串 $s$。
你需要回答 $q$ 次询问,每次询问给出两个整数 $l_i$ 和 $r_i$,要求计算并输出:
$\sum_{j=l_i}^{r_i} f(s[l_i \dots j])$
(其中 $s[l_i \dots j]$ 表示 $s$ 从第 $l_i$ 个字符到第 $j$ 个字符组成的子串)。

这个其实是**方便我们进行计算**的。
**输入格式**
第一行包含一个整数 $t$($1 \le t \le 10^3$),表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $q$($1 \le n \le 10^6$, $1 \le q \le 100$),分别表示字符串长度和询问次数。
第二行包含一个长度为 $n$ 的小写英文字符串 $s$。
接下来 $q$ 行,每行包含两个整数 $l_i$ 和 $r_i$($1 \le l_i \le r_i \le n$),表示一次询问。
保证所有测试用例中 $n$ 的总和不超过 $10^6$。
**输出格式**
对于每次询问,输出一个整数表示表达式的求和结果。
**样例数据**
```
输入:
6
1 1
a
1 1
5 2
aaaaa
1 5
2 4
6 2
abcdef
1 6
3 5
6 3
abaaba
1 6
1 3
2 6
7 3
abcabca
1 7
2 7
4 7
8 3
aababaac
1 8
2 8
3 7
输出:
1
15
6
6
3
14
4
7
12
9
5
13
14
7
```
**样例解释**
在第一个测试用例中,$f(\text{a}) = 1$。
在第二个测试用例中:
对于第一次询问 `1 5`:$f(\text{a}) + f(\text{aa}) + f(\text{aaa}) + f(\text{aaaa}) + f(\text{aaaaa}) = 1 + 2 + 3 + 4 + 5 = 15$。
对于第二次询问 `2 4`(对应的子串是 `aaa`):$f(\text{a}) + f(\text{aa}) + f(\text{aaa}) = 1 + 2 + 3 = 6$。
在第三个测试用例中:
对于第一次询问 `1 6`:$f(\text{a}) + f(\text{ab}) + f(\text{abc}) + f(\text{abcd}) + f(\text{abcde}) + f(\text{abcdef}) = 1 + 1 + 1 + 1 + 1 + 1 = 6$。
对于第二次询问 `3 5`(对应的子串是 `cde`):$f(\text{c}) + f(\text{cd}) + f(\text{cde}) = 1 + 1 + 1 = 3$。
## 思路讲解
[P3375 【模板】KMP(前缀函数)(完全理解 kmp)](/2025/06/25/20250625-86183f59)
队友的这个思路,确实是非常好啊。

```cpp
vector<ll> shortest_prefix(const vector<ll> &pi) {
vector<ll> sp(SZ(pi));
for (int i = 1; i < SZ(pi); ++i) {
if (pi[i] == 0) {
sp[i] = 0;
} else if (sp[pi[i] - 1] > 0) {
sp[i] = sp[pi[i] - 1];
} else {
sp[i] = pi[i];
}
}
return sp;
}
```
这个方法的正确性还是比较容易看出来的,不言自明,只要前缀和后缀相同。其之所以有效,和 kmp 一样。

## AC代码
AC
[https://codeforces.com/contest/2209/submission/367859558](https://codeforces.com/contest/2209/submission/367859558)
::: 源代码
```cpp
/**
* Problem: E. A Trivial String Problem
* Contest: Codeforces Round 1087 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2209/problem/E
* Created: 2026-03-23 13:00:15
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
/*
* 采用 0-based 设计
* 模式串(s2)+'#'+文本串(s1) 需要这样子传入,如果想要执行 kmp 的话
* kmp 模板题 AC https://www.luogu.com.cn/record/269142391
*/
vector<ll> kmp(const string &A) {
// 返回总前缀数组pi
// 其定义是【1;i】真前后缀相同的最短长度
// 特别的,pi【1】=0
vector<ll> pi(SZ(A));
for (int i = 1; i < SZ(A); ++i) {
ll len = pi[i - 1];
while (len > 0 && A[len] != A[i]) {
len = pi[len - 1];
}
if (A[len] == A[i]) {
pi[i] = len + 1;
}
}
return pi;
}
vector<ll> shortest_prefix(const vector<ll> &pi) {
vector<ll> sp(SZ(pi));
for (int i = 1; i < SZ(pi); ++i) {
if (pi[i] == 0) {
sp[i] = 0;
} else if (sp[pi[i] - 1] > 0) {
sp[i] = sp[pi[i] - 1];
} else {
sp[i] = pi[i];
}
}
return sp;
}
void Solve() {
ll N, Q;
cin >> N >> Q;
string s;
cin >> s;
for (int _ = 1; _ <= Q; ++_) {
ll l, r;
cin >> l >> r;
auto pi = kmp(string(s.begin() + l - 1, s.begin() + r));
auto sp = shortest_prefix(pi);
vector<ll> dp(SZ(pi));
ll ans = 0;
for (int i = 0; i < SZ(pi); ++i) {
if (sp[i] == 0) {
dp[i] = 1;
} else {
dp[i] = dp[i - sp[i]] + 1;
}
ans += dp[i];
}
// #ifdef LOCAL
// debug(l);
// debug(r);
// debug1d(sp);
// debug1d(dp);
// cend;
// #endif
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2209/submission/367859558
*/
```
:::
## 心路历程(WA,TLE,MLE……)