[教學][String][Data Structure] 後綴自動機(Suffix Automaton)

==========!! Warning !!==========
此文內容皆是出自自己的理解，若有與實際情況不符之處，請以論文或是大神文章為主
==========!! Warning !!==========

後綴自動機(Suffix Automaton)大概是我見過網路上最多教學資源的資料結構了，許多大陸和外國的神人都有寫教學文，包括寫過持久化資料結構介紹的clj大神。
不過有鑒於許多教學不是為了力求邏輯通順，定義複雜繁瑣，就是講解過程中，省略許多思考步驟，導致讀起來不甚順暢。
最後我還是決定自己完整的給出一篇教學文，使用最少的定義(3個)，盡量簡化構造它和使用它的思考流程，對於重要的性質除非必須，否則說明點到即止，不加以證明。


====================================

如果對於自動機的概念還不是很清楚的人，可以先學學AC自動機(至少我是先學AC自動機的)，了解一下自動機的運作過程和可能用到的性質。
以下不再細講自動機的嚴謹定義和相關性質。

====================================

*名詞解釋：
假設目前有一字串S長度為n，那麼
1.藉著S建出的後綴自動機稱SAM
2.後綴自動機上的狀態u若有連出c的邊達另一狀態，稱為u.ch[c]
3.S[a,b]代表著S[a]~S[b]這段子字串
4.S.Suf(i)代表S[i]~S[n-1]這段後綴，特別的S.Suf(0)=S
之後所提所有的下標都是0 index的

===============正文開始=====================

後綴自動機(Suffix Automaton)是一個以所有S的後綴為接受狀態的自動機。在此先不加證明的給出一些它的性質，讀者可以在讀完全文後重新檢視並感受這些性質：

1.它的狀態數量級是O(n)的 。(實際上，狀態<=2n-1)
  使用後綴自動機的算法會如此高效幾乎都是源自於此線性性質。它對於大部分題目都能有時間複雜度O(n)，空間複雜度O(n)的優秀表現。
2.它的構造複雜度是O(n)的，這源自於插入字元時間複雜度可以達到均攤O(1)。
3.從SAM的根節點出發到任何一個狀態所經過的路徑都會形成S的子字串，同時任何子字串都會對應到SAM上唯一一個狀態。
4.SAM上的每個狀態對應到的字串們一定有後綴包含關係。也就是任兩個字串t1,t2若同屬於某個狀態，要不是t1是t2的後綴，就是t2是t1的後綴

為了理解怎麼建出後綴自動機，我們先把所需要的工具定義清楚。(在此並不用大量的數學符號來描述這些性質，請讀者以感受為主，勿拘泥於形式化的描述)

首先定義一個字串T在字串S上的結束集合End：

End(T,S)={all i | S[i-n+1,i]=T }

例如對於S="dabcab"，T="ab"在S上的結束集合就是{2,5}。

講到這裡，先提供一些結束集合的性質並希望大家先理解並感受一下，之後會看到這對於理解算法是有益的。

1.每個後綴自動機上的狀態都唯一對應著一個結束集合。(如果對這個性質沒什麼感覺，不妨先將它記起來)
2.假設T在字串S上的結束集合是E(同時也是狀態 u)，那麼如果我們不斷的將T的首字元拔掉使得T(=T.Suf(0))變成T.Suf(1)，T.Suf(2)......那麼E或者不變，或者會加入一些元素變得越來越大。(務必記住，結束集合一有變化其實就是狀態有變化)
3.至此，已可由結束集合的定義與性質推出上面的性質4.

重要的是第二個性質。直覺上其實很好理解：如果把某個字串T的首字元不斷拔掉的話，之前在S上有的結束位置不會消失，但是可能會多出一些結束位置。
我們為這個性質特別定義fail函數：

fail(u)= 狀態u所對應的字串T(們)不斷拔掉首字元之後最先會轉移到的結束集合，特別的如果fail(u)不存在則令fail(u)=0。

有了fail之後，如果我們想要遍歷T(對應狀態 u)所有後綴對應到的結束集合的話只須沿著fail函數一直走就可以了。（想一想，為什麼）

隨著fail函數的誕生，我們最後定義Max函數，文字描述如下：

設一狀態u，Max(u)代表著u所對應的所有子字串的最大長度。

什麼意思呢？根據剛剛的討論我們知道字串T(對應狀態 u)在拔掉首字元的過程中，某一段長度區間裡面狀態會是不變的(結束集合不變)，並且結束集合一變動狀態就會轉移到fail(u)。那麼在這長度區間當中最長的子字串的長度便是Max(u)，後面會看到它的用處。

幫助了解，這裡替上面3個定義的函數舉一個實際的例子。
令S="abcbabc",T="abcbab"並且在SAM上對應狀態u0，如果我們開始拔首字元，過程大概會像這樣

T="abcbab",E={5},狀態u0。並且有Max(u0)=6
T="bcbab",E={5},狀態u0。
T="cbab",E={5},狀態u0。
T="bab",E={5},狀態u0。
T="ab",E={1,5},狀態u1。此時知道fail(u0)=u1,Max(u1)=2
T="b",E={1,3,5},狀態u2。fail(u1)=u2,Max(u2)=1
T="",E無意義(說是空集合或是宇集皆可)。fail(u2)=0

至此工具和基本思想已經齊全，以下開始討論如何構造Suffix Automaton。
====================================

*因為狀態和結束集合唯一對應，之後皆以結束集合稱呼狀態

前面已經提到構造法是不斷插入字元來建出SAM，那麼我們就來遞迴(推)的思考構造法：
假設我們已建出S的某個前綴A的Suffix Automaton，而現在要在A的尾端加入字元c，那麼後綴自動機上的結束集合會如何變化呢？
注意到結束位置在A裡面的子字串我們之前都已經處理過了，我們只需要做出結束位置在c的那些新出現的後綴！(並且在未來他們會變成子字串)
剛剛也有提到，我們只需要從A的結束集合開始沿著fail轉移，去觀察這些結束集合的變化就可以了。

現在考慮我們目前在結束集合 u = 字串A所對應到的結束集合(終止狀態)，加入了字元c之後，字串變為Ac，那麼Ac會對應到一個新結束集合N(N={A.length()+1})。
現在會有兩種情況：

1.u沒有連出c的邊
2.u有連出c的邊

其實這等價於

1.之前沒有字串對應u.ch[c]這結束集合
2.之前有字串對應u.ch[c]這結束集合

討論這兩種情況前先插入一個性質，作為對於理解程度的測試：

若u有連出c的邊，那麼世世代代的fail(u)(也就是fail(u),fail(fail(u))...)都有連出c的邊。(若無法理解的話建議反覆閱讀上面的介紹再往下閱讀)

對於第1種情況，我們只需要讓u連出c的邊到N就好了，然後讓u=fail(u)繼續往下；
對於第2種情況，就需要更多的討論。令目前u連出c的邊達結束集合q，即u.ch[c]=q，以下同樣直接給出性質：

1.如果Max(q)=Max(u)+1，那代表結束集合u對應到的所有字串加上字元c，在以前就已經全部出現過了，此時q這個結束集合多了一個元素A.length()+1,實作上直接令fail(N)=q，結束。(請想一下為何不必再沿著u的fail走了)

2.如果Max(q)>Max(u)+1，那代表結束集合u對應到的字串加上字元c並沒有包含q這個結束集合對應到的全部的字串（讀起來有點不順，請盡量理解），我們不得不把q這個結束集合分裂成nq和q兩個結束集合，其中nq滿足Max(nq)=Max(u)+1，而q就是撿剩下那些長度>Max(u)+1的字串的結束集合，因為他們的結束集合不能被更新(他們的結束位置並沒有A.length()+1)。
  nq這個結束集合的信息要如何維護呢？首先Max(nq)=Max(u)+1，nq應該要保留q的所有出邊，fail(nq)要繼承fail(q)，並且fail(q)=fail(N)=nq(想一想，為什麼)

這樣就成功解決了所有的case。

到此為止，構造法講解完畢，細節請參考模板。
add函數的每一行皆有對應上面的討論，可以配合對照。

例題:
SPOJ LCS 題解
SPOJ LCS2 題解
以上兩題可以試著用倍增SA寫寫看，基本上是要TLE的...

SPOJ NSUBSTR 題解
SPOJ SUBLEX 題解
Codeforces 235C 題解 
這些都是作法很多(Suffix Array,Suffix Tree...)，非常經典的問題，可以從中理解SAM的精妙之處。

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;
    }
}SAM;