lessons/参考实现/04-KMP与Manacher/CodeForces-432D.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    int n = static_cast<int>(s.size());
    vector<int> pi(n), occurrences(n + 1);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    for (int x : pi) ++occurrences[x];
    for (int len = n; len >= 1; --len) occurrences[pi[len - 1]] += occurrences[len];
    for (int len = 1; len <= n; ++len) ++occurrences[len];

    vector<int> borders;
    for (int len = n; len > 0; len = pi[len - 1]) borders.push_back(len);
    reverse(borders.begin(), borders.end());
    cout << borders.size() << '\n';
    for (int len : borders) cout << len << ' ' << occurrences[len] << '\n';
}