题目描述

难度分:$2000$

输入长度$\leq 10^5$的字符串$s$，只包含大写英文字母。

对于每个既是$s$前缀又是$s$后缀的子串$t$，计算$t$的长度，以及$t$在$s$中的出现次数。

注意$t$可以等于$s$。

输出格式：

• 第一行，输出有多少种长度不同的$t$。把这个数字记作$k$。
• 然后输出$k$行，每行两个数，分别表示$t$的长度和$t$在$s$中的出现次数。

必须按照$t$长度递增的顺序输出这$k$行。

输入样例$1$

ABACABA

输出样例$1$

3
1 4
3 2
7 1

输入样例$2$

AAA

输出样例$2$

3
1 3
2 2
3 1

算法

$Z$函数+后缀和

设$n$为$s$串的长度，先利用扩展$KMP$算法求出$z$数组，其中的元素$z[i]$就表示后缀$s[n-i…n-1]$的所有前缀中，也是整个$s$串的前缀的最大长度，本质上$cnt$数组就是$s$串一堆前缀的频数。然后开辟一个$cnt$数组来存储$z[i]$的频数，其中$i \in [0,n)$。

因为$s$长度为$i$的前缀是长度为$i+1$、$i+2$、……、$n$的前缀的前缀，此时这么来理解，前缀$s[0…i-1]$都作为$s$中某些后缀的前缀在后面出现，所以$\Sigma_{len=i}^{n}cnt[len]$就是$s$串长度为$i$的前缀在$s$中作为子串一共出现了多少次。因此预处理出$cnt$的后缀和（直接原数组$cnt$上操作即可），遍历$i \in [1,n]$，只要满足$i=z[n-i]$就说明$s$长度为$i$的前缀等于相同长度的后缀，将$(i,cnt[i])$存入答案数组$res$。

最后先输出$res$数组的大小，然后按照第一关键字递增的顺序输出$res$数组的二元组信息就可以了。

复杂度分析

时间复杂度

$Z$函数的时间复杂度为$O(n)$；求$cnt$数组的时间复杂度为$O(n)$；求$cnt$数组的后缀和时间复杂度也是$O(n)$；最后输出结果数组的时间复杂度仍然是$O(n)$。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的字符串，$z$数组、$cnt$数组，以及结果数组$res$都是$O(n)$的空间消耗，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

template<class S>
vector<int> z_algo(const S& s) {
    int n = s.size();
    vector<int> r(n + 1);
    r[0] = 0;
    for(int i = 1, j = 0; i <= n; i++) {
        int& k = r[i];
        k = j + r[j] <= i? 0: min(j + r[j] - i, r[i - j]);
        while(i + k < n and s[k] == s[i + k]) k++;
        if(j + r[j] < i + r[i]) j = i;
    }
    r[0] = n;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> cnt(n + 2);
    vector<int> z = z_algo(s);
    for(int i = 0; i < n; i++) {
        cnt[z[i]]++;
    }
    vector<pair<int, int>> res;
    for(int i = n; i >= 1; i--) {
        cnt[i] += cnt[i + 1];
        if(z[n - i] == i) {
            res.push_back({i, cnt[i]});
        }
    }
    int k = res.size();
    cout << k << '\n';
    for(int i = k - 1; i >= 0; i--) {
        cout << res[i].first << ' ' << res[i].second << '\n';
    }
    return 0;
}