後綴自動機原理。我們考慮如果把壹個字符串的後綴建立壹棵字典樹，那麽其狀態和結點都是O(N^2)級別的。因為不能充分利用字符串本身的特點。我們考慮，假設我們有壹個字符串T，某個串s是其的子串，那麽我們在s後面加入壹些字符就有可能使其變成T的後綴，而如果串s不是T的子串，就沒有必要浪費空間。所以，為了識別所有的後綴，就要盡可能的利用這些可能。後綴自動機是最簡狀態自動機，其狀態數是線性的，可以證明。
我們按照壹定的順序來壹點壹點剖分自動機。
狀態。我們知道，後綴自動機是可以在線構建的。每插入壹個新的字符，在自動機中就會產生壹個新的狀態。我們用State(s)表示已經插入字符串s後所能達到的狀態。每個狀態裏面我們有這樣3個元素。 pre，其指向上壹個可以接收相同後綴的結點，我們不能把這個理解成為指向當前狀態的父親，因為壹個節點可能有許多個“父親”。 len，表示從根節點（空狀態，即為沒有插入任何壹個字符）走到當前點最多要走多少步，也可以理解為在當前狀態下自動機可以識別的最長後綴的長度。next[26]，記錄s已經加入自動機後，再加入壹個字符後，該字符在自動機中的位置。
可以識別。我們說壹個狀態State可以識別某個字符串x，其意思表示為，在自動機中存在從根結點到當前的狀態的壹條路徑，使得串x是這條路徑形成的字符串的壹個子串。
Right集合，我們定義這樣壹個集合：其表示某壹狀態下所有能識別的後綴的右端點位置集合。
舉個例子，比如說對於這樣壹個串T = “aabaaabaaabbab”。可以識別“ab”的的Right集合 S1 = ｛3，7，11，13｝。
在繼續向下之前，先提出壹個註意的地方，就是，當我們達到State(s)時，假設是第壹次達到，那麽此時的自動機是串s的自動機，而不是整個文本串T（s是其的壹個子串）的自動機。壹定要註意語句的主語。
Parent樹。我們先來對其進行壹個如下的分析。
首先對於壹個空串來說，其可識別的位置為所有位置（其實沒有必要，這麽說是為了壹會的圖畫方便些）。
Right（空） = ｛1，2，3，4，5，6，7，8，9，10，11，12，13，14｝；
然後我們考慮長度為1的。
Right（“a”）={1,2,4,5,6,8,9,10,13},
Right("b") = {3, 7, 11, 12, 14}.
接下來， Right（“aa”） = {2, 5, 6, 9, 10}, Right(“ab”) = {3, 7, 11, 14}, Right("bb") = {12}， Right("ba") = {4,8,13}
Right(“aaa”) = {6, 10} Right(“aab”) = {3, 7, 11} Right("aba") = {4, 8} Right("baa") = {5, 9} Right("bba") = {13} Right("bab") = {14} Right("abb") = {12}
Right("aaab") = {7, 11} Right(“aaba”) = {4, 8} Right("abaa") = {5, 9} Right("baaa") = {6, 10} Right("aabb") = {12} Right("abba") = {13} Right("bbab") = {14}
再向下由於人類智慧太不好搞了，就不畫了。但是，根據現有的Right集合，或許我們可以發現些什麽。給出壹張圖來直觀地展示：
我們用小學生看圖找特點的思維來壹點點看這張圖。用羅列的方法來找特點。（嘿嘿，其實 是我的思路比較亂）
1、首先要記住壹件事：樹的深度不等於根到這個節點組成的字符串長度。很明顯的，有幾個單個的葉子結點很好的說明了這個特點。
2、到某個節點組成的字符串的長度越長，其Right集合裏面的元素就越少，也就是說，其在串中的可以匹配的位置就越少。
3、壹個節點的Right集合大小等於以其為根的子樹的葉子結點的個數。（這個好像不太明顯，因為 我沒有把整個樹畫完QAQ……不過大家可以自行向下擴展）
4、葉子結點除外，根到壹個結點組成的字符串的長度等於其父親的長度加 + 1，但是我們要清楚的知道，父親的長度是指其Right集合所表示的所有字符串的最長長度。舉個例子來說，對於這樣壹個串，“AABAABAAB“，Rigth("AB") = ｛3，6，9｝ Right(”ABB“) = ｛3，6，9｝，他們的Right集合是相同的。所以，用這個也可以來解釋 第1 點。樹的深度不等於根到這個節點組成 的字符串的長度。
5、壹個非葉結點至少有兩個兒子。
6、兩個不同的Right集合，其關系要麽是壹個是另壹個的真子集，要麽兩個完全不相交。在樹上這個是很直觀的吧。
我們再來理解壹下pre指針的作用。
某個狀態的pre指針指向的結點是當前結點（cur）Right集合所表示的字符串的最長公***後綴（不是其本身）
好，下面我們來具體說明壹下構建自動機的過程：
在這個過程中我們需要兩個指針，last表示上壹次插入的結點位置，cur表示當前的結點位置。
1、首先是建立壹個空結點，表示空串的狀態，其len = 0, pre = null；這個是很好理解的吧，在Parent樹中，這個結點的角色是樹根。
2、然後假設我們已經構建了前i-1個字符的後綴自動機，現在我們考慮加入第i個字符 x。首先先從last 向 cur連接壹條邊為x的出邊，然後cur.len = last.len + 1,這些都是很顯然的吧。
3、好，現在我們需要確定cur的pre指針的指向。我們現在在Parent樹上沿著last的pre指針向上跳。
如果不小心跳到了NULL，說明當前自動機中沒有x這個字符，那麽很好處理，直接把cur的pre指針指向root,註意是root，而不是NULL。
如果沒有跳到NULL，那麽,如果last->pre沒有x這樣壹條出邊。那麽這情況好說，直接從last->pre向cur連壹條為x的出邊。為什麽要這麽連？我們考慮，我們已知last->pre指向的是當前狀態Right集合所表示的所有字符串的最長公***後綴，我們在當前狀態的字符串後加上了壹個新的字符x，那就相當於在所有的後綴後面都加了壹個x，但是為了保證不重復不遺漏的在後綴上加上這個字符x，所以我們要選擇最長的那個來添加，這樣自然就用到了這個pre指針， 跳到最長後綴的地方。
如果last->pre有這樣壹條出邊。那麽我們就要分兩種情況來討論：
我們用p來代表last->pre，用q來代表last->pre的x出邊。
情況1. 如果q.len == p.len + 1,那麽就把cur的pre設為q。
情況2. 如果q.len > p.len + 1，那麽就要把拷貝壹個新的結點。
情況壹情況二的解釋如下：（來自王夢迪（NOI2015金牌得主）的博客）
第二種情況——當我們進入壹個已存在的轉移(p,q)時。這意味著我們試圖向字符串中添加字符x+c（其中x是字符串s的某壹後綴，長度為len(p)），且該字符串先前已經被加入了自動機（即，字符串x+c已經作為子串包含在字符串s中）。因為我們假設字符串s的自動機已被正確構建，我們並不應該添加新的轉移。然而，cur的後綴鏈接指向哪裏有壹定復雜性。我們需要將後綴鏈接指向壹個長度恰好和x+c相等的狀態，即，該狀態的len值必須等於len(p)+1.但這樣壹種情況可能並不存在：在此情況下我們必須添加壹個“分割的”狀態。
因此，壹種可能的情形是，轉移(p,q)變得連續，即，len(q)=len(p)+1.在這種情況下，事情變得簡單，不必再進行任何分割，我們只需要將cur的後綴鏈接指向q。
另壹種更復雜的情況——當轉移不連續時，即len(q)>len(p)+1.這意味著狀態q不僅僅匹配對我們必須的，長度len(p)+1的子串w+c，它還匹配壹個更長的子串。我們不得不新建壹個“分割的”狀態q：將子串分割成兩段，第壹段將恰在長度len(p)+1處結束