[SPOJ NSUBSTR][Suffix Automaton] NSUBSTR - Substrings

題目連結

恩....一樣是個只給O(n)方法過的字串題，倍增算法之類的只能吃土了QQ
後綴自動機的介紹請參考 這裡

此題是要求出某字串所有長度的子串的最大出現次數
還是老規矩，先把後綴自動機建出，那麼只需要想到本題所需的重點性質就可以出解了
三個提示：
1.每個狀態都代表著一個結束集合，這個結束集合的大小就是這個狀態有幾個結束位置
2.別忘了Max的定義。既然我們知道某狀態之中最大長度的子串有Max那麼長，那麼<=Max的子串的出現次數就可以用本狀態的結束集合大小去更新
3.結束集合的大小可以用類似DP的方法去遞推，方法很多種，這裡採用計數排序求拓樸序的方法
複雜度:計數排序O(n)+SAM O(n)+遍歷 O(n)，總而言之SPOJ就是要你O(n)就對了(?

#include<bits/stdc++.h>
using namespace std;
const int maxlen=250000+5;
const int maxnode=500000+5;
const int SIGMA_SIZE=26;
struct Node
{
    Node *fail,*ch[SIGMA_SIZE];
    int Max,End;
    vector<int> Ch;
    Node() {memset(ch,0,sizeof ch);Max=End=0;fail=0;Ch.clear();}
} mem[maxnode],*root,*last;
struct SuffixAutomaton
{
    int size;
    inline int idx(char c) {return c-'a';}
    inline void init(){size=0;root=last=&mem[0];}
    inline void add(char c)
    {
        c=idx(c);
        Node *p=last;
        Node *np=&mem[++size];np->Max=p->Max+1;
        while(p && !p->ch[c]) {p->Ch.push_back(c);p->ch[c]=np,p=p->fail;}
        if(!p) np->fail=root;
        else
        {
            Node *q=p->ch[c];
            if(q->Max==p->Max+1) np->fail=q;
            else
            {
                Node *nq=&mem[++size];nq->Max=p->Max+1;
                memcpy(nq->ch,q->ch,sizeof(q->ch));
                nq->fail=q->fail;
                np->fail=q->fail=nq;
                while(p && p->ch[c]==q) p->ch[c]=nq,p=p->fail;
            }
        }
        last=np;
    }
    int C[maxnode],ord[maxnode];
    void topo()
    {
        for(int i=0;i<=size;i++) C[(&mem[i])->Max]++;
        for(int i=1;i<=size;i++) C[i]+=C[i-1];
        for(int i=0;i<=size;i++) ord[--C[(&mem[i])->Max]]=i; 
    }
    int ans[maxlen];
    void cal(Node* now)
    {
        if(now->fail) now->fail->End+=now->End;
        ans[now->Max]=max(ans[now->Max],now->End);
    }
    void print(int n)
    {
        int now=0;
        for(int i=n;i>=1;i--)
        {
            now=max(now,ans[i]);
            ans[i]=max(ans[i],now);
        }
        for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    }
}SAM;
char s[maxlen];
int main()
{
    SAM.init();
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;i++) SAM.add(s[i]);
    Node *now=root;
    for(int i=0;i<n;i++)
    {
        int c=SAM.idx(s[i]);
        now=now->ch[c];
        now->End=1;
    }
    SAM.topo();
    for(int i=SAM.size;i>=0;i--) SAM.cal(&mem[SAM.ord[i]]);
    SAM.print(n);
}