spoj 8222 Substrings（后缀自动机）

题目链接：spoj 8222 Substrings

代码

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

using namespace std;
typedef long long ll;
const int maxn = ;
const int SIGMA_SIZE = ;

struct SAM {
    int sz, last;
    int g[maxn<<][SIGMA_SIZE], pre[maxn<<], step[maxn<<];
    int pos[maxn<<], right[maxn<<], cnt[maxn<<];

    void newNode(int s) {
        step[++sz] = s;
        pre[sz] = ;
        memset(g[sz], , sizeof(g[sz]));
    }

    int idx(char ch) { 
        if (ch >= 'A' && ch <= 'Z') return ch - 'A' + ;
        return ch -'a';
    }

    void init() {
        sz = , last = ;
        newNode();
    }

    void insert(char ch);
    void get_tuopu();
    void get_right(char* str);

    int f[maxn];
    void solve (int n) {
        memset(f, , sizeof(f));
        for (int i = ; i <= sz; i++) {
            int u = step[i];
            f[u] = max(f[u], right[i]);
        }

        for (int i = n-; i; i--)
            f[i] = max(f[i], f[i+]);
        for (int i = ; i <= n; i++)
            printf("%d\n", f[i]);
    }
}SA;

int K;
char s[maxn];

int main () {
    scanf("%s", s);
    SA.init();
    int n = strlen(s);
    for (int i = ; i < n; i++)
        SA.insert(s[i]);
    SA.get_tuopu();
    SA.get_right(s);
    SA.solve(n);
    return ;
}

void SAM::insert(char ch) {
    newNode(step[last] + );
    int v = idx(ch), p = last, np = sz;

    while (p && !g[p][v]) {
        g[p][v] = np;
        p = pre[p];
    }

    if (p) {
        int q = g[p][v];
        if (step[q] == step[p] + )
            pre[np] = q;
        else {
            newNode(step[p] + );
            int nq = sz;
            for (int j = ; j < SIGMA_SIZE; j++) g[nq][j] = g[q][j];

            pre[nq] = pre[q];
            pre[np] = pre[q] = nq;

            while (p && g[p][v] == q) {
                g[p][v] = nq;
                p = pre[p];
            }
        }
    } else
        pre[np] = ;
    last = np;
}

void SAM::get_tuopu() {
    for (int i = ; i <= sz; i++) cnt[i] = ;
    for (int i = ; i <= sz; i++) cnt[step[i]]++;
    for (int i = ; i <= sz; i++) cnt[i] += cnt[i-];
    for (int i = ; i <= sz; i++) pos[cnt[step[i]]--] = i; 
}

void SAM::get_right(char* str) {
    int p = , n = strlen(str);
    for (int i = ; i <= sz; i++) right[i] = ;

    for (int i = ; i < n; i++) {
        int v = idx(str[i]);
        p = g[p][v];
        right[p]++;
    }

    for (int i = sz; i; i--) {
        int u = pos[i];
        right[pre[u]] += right[u];
    }
}