13576_Prefix와 Suffix

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
 
vector<int> sfx, g, ng, lcp, idx, cnt;
string s;
int N, pos[100010];
vector<pair<int, int>> ans;
 
bool comp(int& i, int& j, int t) {
    if (g[i] == g[j]) return g[i + t] < g[j + t];
    return g[i] < g[j];
}
 
void getsfx() {
    int lim = max(256, N + 1);
    sfx.clear(); g.clear(); ng.clear(); idx.clear();
    sfx.resize(N); g.resize(N + 1); ng.resize(N + 1); idx.resize(N + 1);
 
    for (int i = 0; i < N; ++i) {
        g[i] = s[i];
        sfx[i] = i;
    }
 
    if (N == 1) g[0] = 1;
 
    for (int t = 1; t < N; t <<= 1) {
        cnt.clear(); cnt.resize(lim + 1);
        for (int i = 0; i < N; ++i) cnt[g[min(i + t, N)]]++;
        for (int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
        for (int i = N - 1; i >= 0; --i) idx[--cnt[g[min(i + t, N)]]] = i;
 
        cnt.clear(); cnt.resize(lim + 1);
        for (int i = 0; i < N; ++i)  cnt[g[i]]++;
        for (int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
        for (int i = N - 1; i >= 0; --i) sfx[--cnt[g[idx[i]]]] = idx[i];
        
        ng[sfx[0]] = 1;
        for (int i = 1; i < N; ++i) {
            ng[sfx[i]] = ng[sfx[i - 1]] + comp(sfx[i - 1], sfx[i], t);
        }
        for (int i = 0; i < N; ++i) g[i] = ng[i];
        if (ng[sfx[N - 1]] == N) break;
    }
    for (int i = 0; i < N; ++i) --g[i];
}
 
void getlcp() {
    lcp.clear(); lcp.resize(N + 1);
    for (int i = 0, k = 0; i < N; ++i, k = max(k - 1, 0)) {
        if (g[i] == N - 1) continue;
        for (int j = sfx[g[i] + 1]; s[j + k] == s[i + k]; ++k);
        lcp[g[i]] = k;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> s;
    N = s.length();
 
    getsfx();
    getlcp();
 
    int minn = 1e9, cnt = 1;
    for (int i = g[0] - 1; i >= 0 && lcp[i]; --i) {
        minn = min(lcp[i], minn);
        cnt++;
        if (N - sfx[i] == minn) ans.push_back({ N - sfx[i], cnt });
    }
 
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); ++i) {
        pos[ans[i].first] = i+1;
    }
 
    minn = 100001, cnt = 1;
    for (int i = g[0]; i < N - 1 && lcp[i]; ++i) {
        if (minn > lcp[i]) {
            if (pos[minn]) {
                ans[pos[minn] - 1].second += cnt-1;
                pos[minn] = 0;
            }
            minn = lcp[i];
        }
        cnt++;
        if (N - sfx[i+1] == minn) ans.push_back({ N - sfx[i+1], cnt });
    }
    
    if (pos[minn]) {
        ans[pos[minn] - 1].second += cnt-1;
        pos[minn] = 0;
    }
 
    ans.push_back({ N, 1 });
    
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i.first << ' ' << i.second << '\n';
    }
 
}