[SPOJ LCS2][Suffix Automaton] LCS2 - Longest Common Substring II

題目連結

跟 LCS 這篇的作法非常相似，基本概念就不說了
不過寫這題的時候花了頗大量的時間釐清答案的更新順序和debug(最後的bug竟然是錯在toposort寫爛了...)

難點在於要怎麼兩兩合併計算答案，這要對後綴自動機上的狀態表示感受到一定深度才能體會(?
code中的許多assert可以幫助理解一些關鍵點和常有的bug


 首先為了在後綴自動機上保留那些已經匹配過的字串的結果，我們在每一個狀態上用minlen表示目前為止這個狀態能匹配的最大長度(有點拗口xD)

用curcnt來表示正在匹配的這個字串在後綴自動機上的匹配長度，容易知道最後minlen是要和curcnt取min的
最後剩下一個頗重要的細節就是對於某個狀態若匹配長度>0，那麼他世世代代的fail狀態都可以用他們的Max來更新自己的curcnt(回想一下faillink的定義，可參考下面code的某一行assert)
總時間複雜度O(n) 空間複雜度O(n)，表現非常優秀，而且SPOJ幾乎就只讓這種算法過了......

#include<bits/stdc++.h>
using namespace std;
const int maxnode=200000+5;
const int maxlen=100000+5;
const int INF=(1<<30);
const int SIGMA_SIZE=26;
struct Node
{
    Node *fail,*ch[SIGMA_SIZE];
    int Max,curcnt,minlen,vis;
    Node() {Max=curcnt=vis=0;minlen=INF;fail=0;memset(ch,0,sizeof ch);}
}*root,*last,mem[maxnode];
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[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 order;
    Node* ord[maxnode];
    bool dfs(Node* now)
    {
        now->vis=-1;
        if(now->fail)
        {
            if(now->fail->vis==-1) return 0;
            else if(now->fail->vis==0 && !dfs(now->fail)) return 0;
        }
        now->vis=1;
        ord[order++]=now;
        return 1;
    }
    void topo()
    {
        order=0;
        for(int i=0;i<=size;i++)
        {
            Node* now=&mem[i];
            if(now->vis==1) continue;
            assert(dfs(now));
        }
    }


/*  Another method!!
    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=size;i>=0;i--) ord[--C[mem[i].Max]]=i;
    }
*/
    inline void addS(char* s)
    {
        for(int i=0;i<=size;i++) mem[i].curcnt=0;
        int n=strlen(s),cnt=0;
        Node *now=root;
        for(int i=0;i<n;i++)
        {
            int c=idx(s[i]);
            if(now->ch[c]) cnt++,now=now->ch[c];
            else
            {
                while(now && !now->ch[c]) now=now->fail;
                if(now) cnt=now->Max+1,now=now->ch[c];
                else now=root,cnt=0;
            }
            now->curcnt=max(now->curcnt,cnt);
        }
        for(int i=0;i<=size;i++) mem[i].vis=0;
        for(int i=size;i>=0;i--)
        {
            //now=&mem[ord[i]];
            now=ord[i];now->vis=1;
            now->minlen=min(now->minlen,now->curcnt);
            assert(!now->fail || now->fail->vis==0);
            if(now->fail && now->curcnt) now->fail->curcnt=max(now->fail->curcnt,now->fail->Max);
        }
    }
}SAM;
char s[maxlen];
int main()
{
    SAM.init();
    scanf("%s",s);
    int n=strlen(s),ans;
    for(int i=0;i<n;i++) SAM.add(s[i]);SAM.topo();
    while(scanf("%s",s)==1) SAM.addS(s);
    ans=0;
    for(int i=0;i<=SAM.size;i++) ans=max(ans,mem[i].minlen);
    printf("%d\n",ans);
}