Codeforces Round 1087 (Div. 2)——CF-2209-E. A Trivial String Problem（如何计算最短 border？）

题目大意

题目描述

定义函数 $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）

队友的这个思路，确实是非常好啊。

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

源代码

/**
 * 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……）