题目链接：Codeforces 432D

你有一个字符串 $S$，你需要求出所有匹配的前后缀，并计算出这些前后缀在字符串中出现的次数。

数据范围：$1 \le \lvert S \rvert \le 10 ^ 5$。

Solution

对于问题一，我们可以轻易地使用 $\text{KMP}$ 算法解决。答案就是从 $n$ 通过 $next$ 数组跳到 $1$ 的次数。

对于问题二，我们设 $f(i)$ 表示前缀 $i$ 在字符串中出现了多少次。初始状态为 $f(i) = 1(1 \le i \le \lvert S \rvert)$，显然有转移 $f(i) \rightarrow f(next(i))$。

时间复杂度：$\mathcal O(\lvert S \rvert)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e5 + 5;

int n, nxt[N], pos[N], f[N];
char s[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= n; i++) {
        for (; j && s[j + 1] != s[i]; j = nxt[j]);
        if (s[j + 1] == s[i]) j++;
        nxt[i] = j;
    }
    int tot = 0;
    for (int i = n; i; i = nxt[i]) {
        pos[++tot] = i;
    }
    std::fill(f + 1, f + n + 1, 1);
    for (int i = n; i >= 1; i--) {
        f[nxt[i]] += f[i];
    }
    printf("%d\n", tot);
    for (int i = tot; i >= 1; i--) {
        printf("%d %d\n", pos[i], f[pos[i]]);
    }
    return 0;
}