某島

… : "…アッカリ~ン . .. . " .. .
March 19, 2020

SPOJ NSUBSTR. Substrings

後綴自動機 + fail 樹 DP。

const int N = int(5e5) + 9, Z = 26;

namespace SAM{

    int trans[N][Z],par[N],len[N],cnt[N],tail,tot;
    char buf[N];

    int new_node(){
        RST(trans[tot]);
        return tot++;
    }
    int new_node(int u){
        CPY(trans[tot],trans[u]),par[tot]=par[u];
        return tot++;
    }
#define v trans[u]
#define p par[u]
#define pp par[uu]

    int Ext(int c){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }

        return tail = uu;
    }

#define c (*cur - 'a')

    void Init(){
        tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) cnt[Ext(c)] = 1;
    }

    VI adj[N]; int f[N];

    void dfs(int u = 0){
        ECH(it, adj[u]){
            dfs(*it);
        }
        cnt[p] += cnt[u];
        checkMax(f[len[u]], cnt[u]);
    }

    int Run(){
        int n = len[tail];
        FOR(u, 1, tot) adj[p].PB(u); dfs();
        REP_1(i, n) OT(f[i]);
    }

} using namespace SAM;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Init(), Run();
}