[SPOJ LCS][Suffix Automaton] LCS - Longest Common Substring

原題連結

Suffix Automaton(後綴自動機)的初級練習題，關於Suffix Automaton的教學和介紹網路上有很多資源，我之後也會自己補上一篇的
這題會用SAM的主要原因是SPOJ會莫名的把O(nlogn)的Suffix Array解卡掉，所以能過的大概只有後綴自動機或是O(n)後綴樹、後綴陣列的構造法吧

回到題目，題目要求是求出兩個字串的最常公共子串
先把第一個字串建造出後綴自動機
然後遍歷第二個字串，相當於在後綴自動機上轉移狀態，假設目前遍歷到s[i]=c：

1.若當前狀態有連出c的邊，則轉移到該狀態並且cnt++
2.若沒有連出c的邊，則沿著Fail link往回走直到有連出c的邊或是now=0
    2-1.若now=0，則cnt<-0,now<-root;
    2-2.否則cnt<-now->Max+1,now<-now->ch[c];

參考後綴自動機的性質和複雜度證明很容易得知這樣做的正確性和效率，就不贅述了
SPOJ上還有進階版 LCS2 ，顯示了後綴自動機是多麼強大的東西......

#include<bits/stdc++.h>
using namespace std;
const int maxlen=250000+5;
const int maxnode=1000000+5;
const int SIGMA_SIZE=26;
struct Node
{
    Node *fail,*ch[SIGMA_SIZE];
    int Max;
    Node() {Max=0,fail=0;memset(ch,0,sizeof ch);}
} node[maxnode],*root,*last;
struct SuffixAutomaton
{
    int size;
    inline int idx(char c) {return c-'a';}
    inline void init() {size=0;last=root=&node[0];}
    inline void add(char c)
    {
        c=idx(c);
        Node *p=last;
        Node *np=&node[++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=&node[++size];nq->Max=p->Max+1;
                memcpy(nq->ch,q->ch,sizeof(q->ch));
                nq->fail=q->fail;
                q->fail=np->fail=nq;
                while(p && p->ch[c]==q) p->ch[c]=nq,p=p->fail;
            }
        }
        last=np;
    }
    void solve(char* s)
    {
        int n=strlen(s),ans=0,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 cnt=0,now=root;
            }
            ans=max(ans,cnt);
        }
        printf("%d\n",ans);
    }
}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]);
    scanf("%s",s);
    SAM.solve(s);
}