[SPOJ LCS2]LCS2 - Longest Common Substring II

此篇題解必須先熟悉後綴自動機的操作才能看懂
關於詳細的後綴自動機圖文教學，請參考這裡

簡單來說，題目給你一堆字串$S_{i}$ ($1\leq i\leq N\leq 10$)，要你求這些$S_{i}$最長的公共子字串長度

可以考慮先對$S_{1}$建立一個後綴自動機，這樣就只有$S_{1}$的子字串能夠被這個自動機接受了
之後每輸入一個字串$S_{i}$，就維護這個自動機，讓這個自動機只接受$S_{1}、S_{2}、...、S_{i}$的共同子字串

真的可行嗎？

我們先回顧一下只有兩個字串$A$和$B$時，找出$A$和$B$的最大共同子字串長度的方法
先對$A$建立後綴自動機，然後用$B$去嘗試在自動機裡面轉移
當轉移失敗時就沿著失配邊走一步，再繼續嘗試轉移

可以發現
每成功轉移一次，代表找到長度多$1$的共同子串
每沿著失配邊走一步，目前找到的共同子串長度就變為走到的節點的$max\_len$

而過程中走到的每一個節點和其沿著失配邊可以走到的所有點，每個點代表的字串集合聯集起來就恰好是$A$和$B$的共同子字串了，不多也不少

咦？真的嗎？

注意剛剛這句話：「每成功轉移一次，代表找到長度多$1$的共同子串」
因此就算目前找到了長度$x$的共同子串，不一定代表目前節點的$max\_len=x$ (但可以保證$max\_len\geq x$)

只有兩個字串時，只要持續更新找到共同子串的最大長度即可，因此這個問題可以忽略

但是這題要求處理多個字串，因此我們必須面對這個問題，否則會多考慮一些情況
回想建立後綴自動機的過程，好像也遇過同樣的問題耶！
都是因為某個節點代表的字串集合中有些是不想要的

因此，解決方法也一樣
把想要的點分離出來！

code中的Node *Split(Node *cur,const int c)就是回傳分離出來的點

因此，先對$S_{1}$建立一個後綴自動機，這樣就只有$S_{1}$的子字串能夠被這個自動機接受了
之後每輸入一個字串$S_{i}$，就維護這個自動機，讓這個自動機只接受$S_{1}、S_{2}、......、S_{i}$的共同子字串
方法是讓$S_{i}$在自動機裡面轉移，並藉由分裂點的方式確保走到的每個點和其沿著失配邊可以走到的點所包含的字串集合，聯集起來就恰好是所有的共同子串
每轉移一次最多需要分裂一次點，因此讓$S_{i}$進行轉移的時間複雜度是$\left|S_{i}\right|$

至於轉移完之後要怎麼維護讓這個自動機以後只接受$S_{1}、S_{2}、......、S_{i}$的共同子字串呢？
我們先把所有走過的點標記起來，這些點和其沿著失配邊可以走到的點都必須被保留下來，而其他的必須刪除

可以發現，把所有的失配邊反向後會形成一棵樹，因此可以用一個$queue$儲存所有樹葉，每當$S_{i}$加入完成後，就可以每個樹葉檢查看看能不能刪除
不能的話加入下一個$queue$供下次使用
可以的話將這個節點標記為刪除 (直接$delete$釋放記憶體會出錯。想一想，為甚麼XD)
當一個節點的所有子節點都被刪除了，這個節點就成了樹葉，必須被加入$queue$接受檢查

其實，上面的做法還忘記考慮一點：那分裂出來的點會不會成為新的樹葉呢？
答案是不會的 (想一想，為甚麼XD)

要實作上述過程，必須先做不少的預處理、建立並在適當的時機維護一些資訊，之後才能達到所需的複雜度 (複雜度是不允許有$\log$的)

因此，加入$S_{i}$的時間複雜度怎麼算呢？
首先必須先花費$O(\left|S_{i}\right|)$來進行轉移並視需要分裂一些點
然後再用$O(\left|S_{1}\right|)$來檢查所有的葉節點要不要刪除
這只是檢查
整個刪除葉子的過程的時間複雜度總共是$O(\sum_{i=1}^{N}\left|S_{i}\right|)$

總時間複雜度：$O(\left|S_{1}\right|+\sum_{i=2}^{N}\left|S_{i}\right|+(N-1)\left|S_{1}\right|+\sum_{i=1}^{N}\left|S_{i}\right|)\approx O(N\left|S_{1}\right|+\sum_{i=1}^{N}\left|S_{i}\right|)$

code:

#include<cstdio>
#include<cassert>
#include<string>
#include<queue>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
struct Node
{
    Node *green,*edge[26];
    int max_len;
    int vis,degree;
    bool deleted;
    void SetGreen(Node *o)
    {
        if(green)green->degree--;
        (green=o)->degree++;
    }
}*ROOT,*LAST,BUFFER[200001+100000*10],*NEW;
Node *NewNode(const int _max_len)
{
    NEW->green=NULL;
    NEW->max_len=_max_len;
    NEW->vis=0,NEW->degree=0;
    NEW->deleted=false;
    for(int i=0;i<26;i++)NEW->edge[i]=NULL;
    return NEW++;
}
Node *Split(Node *cur,const int c)
{
    Node *pgreen=cur->edge[c];
    Node *wish=NewNode(cur->max_len+1);
    for(;cur&&cur->edge[c]==pgreen;cur=cur->green)cur->edge[c]=wish;
    for(int i=0;i<26;i++)wish->edge[i]=pgreen->edge[i];
    wish->SetGreen(pgreen->green);
    pgreen->SetGreen(wish);
    return wish;
}
void Extend(const int c)
{
    Node *cur=LAST;LAST=NewNode(LAST->max_len+1);
    for(;cur&&!cur->edge[c];cur=cur->green)cur->edge[c]=LAST;
    if(!cur)LAST->SetGreen(ROOT);
    else
    {
        Node *pgreen=cur->edge[c];
        if(pgreen->max_len==cur->max_len+1)LAST->SetGreen(pgreen);
        else LAST->SetGreen(Split(cur,c));
    }
}
queue<Node*>LEAF[2];
char S[100001];
void Print(Node *o,string now)
{
    if(!o||o->deleted)return;
    puts(now.c_str());
    for(int i=0;i<26;i++)Print(o->edge[i],now+(char)('a'+i));
}
int main()
{
//    freopen("in.txt","r",stdin);
    NEW=BUFFER;
    assert(scanf("%s",S)==1);
    ROOT=LAST=NewNode(0);
    for(int i=0;S[i];i++)Extend(S[i]-'a');
    assert(LEAF[0].empty()&&LEAF[1].empty());
    for(Node *cur=BUFFER;cur!=NEW;cur++)if(!cur->degree)LEAF[0].push(cur);
//    printf("LEAF[0].size()=%d\n",(int)LEAF[0].size());
    int d=0;
    for(int n=1,ans=LAST->max_len;;n++,d^=1)
    {
        if(scanf("%s",S)!=1){printf("%d\n",ans);break;}
        ans=0;
        int now=0;
        Node *cur=ROOT;cur->vis=n;
        for(int i=0;S[i];i++)
        {
            assert(now==cur->max_len);
            const int c=S[i]-'a';
            for(;cur!=ROOT&&(!cur->edge[c]||cur->edge[c]->deleted);cur=cur->green,now=cur->max_len);
            if(cur->edge[c]&&!cur->edge[c]->deleted)
            {
                if(cur->edge[c]->max_len>now+1)cur=Split(cur,c);
                else cur=cur->edge[c];
                now++;
            }
            cur->vis=n;
            getmax(ans,now);
        }
        while(!LEAF[d].empty())
        {
            Node *u=LEAF[d].front();LEAF[d].pop();
            assert(!u->degree&&!u->deleted);
            if(u->vis<n)
            {
                u->deleted=true;
                if(!--(u->green->degree))LEAF[d].push(u->green);
            }
            else LEAF[d^1].push(u);
        }
//        printf("\nn=%d***************\n",n);
//        Print(ROOT,"");
    }
    return 0;
}