後綴自動機 (SAM) 圖文教學 (二)

請先參考後綴自動機 (SAM) 圖文教學 (一)

(Copyright：圖片轉載請註明來源網址，感謝～)

說明：
用兩個「$"$」框起來的東西是字串
用兩個「$'$」框起來的東西是字元 (在這裡等價於單純的英文字母)
「路徑$"abcd"$」代表字串$"abcd"$在圖上會走過的一條路徑
「字串集合」代表很多字串 (?)

還記得這張圖嗎？這是$S="abcd"$時預處理出來的樹

信不信，我可以把這張圖從$11$個節點縮到只剩$5$個節點，並且沒有讓圖喪失任何功能！
想知道怎麼做嗎？答案在這裡：

雖然這樣圖就不是一棵樹了
不過，還是可以依照上一篇講的方式走
舉個例子，子字串$"abc"$、$"bc"$、$"c"$都會走到$3$ (每個節點下面的那些字串集合就是會走到這個點的字串集合)
可以發現
$"a"$的所有後綴都會走到$1$
$"ab"$的所有後綴都會走到$2$
$"abc"$的所有後綴都會走到$3$
$"abcd"$的所有後綴都會走到$4$

那我們就來嘗試讓這個圖保有這個性質
讓$i$代表$S_{1\sim i}$的所有後綴！($S_{1\sim i}$代表$S$的前$i$個字母組成的字串)

那麼要怎麼讓程式知道要這樣建圖呢？

我們先將字母一個一個加進去，看看圖會怎麼長
加入邊$'a'$，讓路徑$"a"$會走到新節點$1$，這時$1$代表了$"a"$：

加入邊$'b'$，讓路徑$"ab"$會走到新節點$2$，這時$2$代表了$"ab"$ (因為是從$1$走過來的，因此代表了$"a"$再加一個$'b'$)：

$2$還差一個$"b"$就能代表$"ab"$的所有後綴了
為了讓$2$代表$"ab"$的所有後綴，我們必須再讓路徑$"b"$連到$2$：

加入邊$'c'$，讓路徑$"abc"$會走到新節點$3$，這時$3$代表了$"abc"$和$"bc"$ (因為是從$2$走過來的，因此代表了$"ab"$和$"b"$再加一個$'c'$)：

$3$還差一個$"c"$就能代表$"abc"$的所有後綴了
為了讓$3$代表$"abc"$的所有後綴，我們必須再讓路徑$"c"$連到$3$：

加入邊$'d'$，讓路徑$"abcd"$會走到新節點$4$，這時$4$代表了$"abcd"$、$"bcd"$和$"cd"$ (因為是從$3$走過來的，因此代表了$"abc"$、$"bc"$和$"c"$再加一個$'d'$)：

$4$還差一個$"d"$就能代表$"abcd"$的所有後綴了
為了讓$4$代表$"abcd"$的所有後綴，我們必須再讓路徑$"d"$連到$4$：

就這麼簡單，我們建完了$"abcd"$的圖！

但是，畢竟$"abcd"$是相對簡單的字串 (每個字母只有出現一次)
下一篇將討論$"abaab"$怎麼建圖！