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

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

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

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

$"abaab"$的圖要怎麼建呢？
我們可以照著上一篇的思路，一個字母一個字母慢慢加

依序加入邊$'a'$和邊$'b'$的過程和上一篇一模模一樣樣，若已經忘記了可以翻回去回顧一下呦～
依序加完邊$'a'$和邊$'b'$時圖會長這樣：

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

$3$還差一個$"a"$就能代表$"aba"$的所有後綴了
為了讓$3$代表$"aba"$的所有後綴，我們必須再讓路徑$"a"$連到$3$
可是問題來了，路徑$"a"$已經存在了，會走到$1$！
怎麼辦呢？
沒關係，我們先製造一種特殊的邊，這條邊可以把連向的點代表的字串集合全部加到連出的那點！
不過為了杜絕濫用行為 (?)，每個點最多只能連出一條這種特殊的邊
這種特殊的邊就畫成綠色的吧，而因為這條邊被加入的字串集合也寫成綠色的
從$3$到$1$連一條這種綠色的邊，圖就會變這樣：

加入邊$'a'$，讓路徑$"abaa"$會走到新節點$4$，這時$4$代表了$"abaa"$和$"baa"$ (因為是從$3$走過來的，因此代表了$"aba"$和$"ba"$再加一個′a′)
注意，$3$代表的字串集合裡面，$"a"$是綠色的，代表路徑$"a"$不是真的走到$3$，因此當然也不能直接藉由加一條邊$'a'$讓路徑$"aa"$走到$4$
所以，$4$目前只有代表$"abaa"$和$"baa"$：

$4$還差$"aa"$和$"a"$就能代表$"abaa"$的所有後綴了
我們先讓路徑$"aa"$連到$4$
這時$4$代表了$"abaa"$、$"baa"$和$"aa"$ (因為是從$3$和$1$走過來的，因此代表了$"aba"$、$"ba"$和$"a"$再加一個$′a′$)
現在圖長這樣：

一樣的問題又出現了，路徑$"a"$已經存在了，會走到$1$！
套用一樣的老方法，從$4$到$1$連一條綠色的邊：

加入$'b'$，讓路徑$"abaab"$會走到新節點$5$，這時$5$代表了$"abaab"$、$"baab"$和$"aab"$ (因為是從$4$走過來的，因此代表了$"abaa"$、$"baa"$和$"aa"$再加一個$′b′$)
注意，$4$代表的字串集合裡面，$"a"$是綠色的，代表路徑$"a"$不是真的走到$4$，因此當然也不能直接藉由加一條邊$'b'$讓路徑$"ab"$走到$5$
所以，$5$目前只有代表$"abaab"$、$"baab"$和$"aab"$：

一樣的問題又出現了，代表$"ab"$的路徑已經存在了，會走到$2$！
一樣，套用老方法，從$5$到$2$連一條綠色的邊：

於是，$"ab"$和$"b"$都被加進了$5$代表的字串集合裡面
現在$5$已經代表了$"abaab"$的所有後綴！
就這麼簡單，我們建完了$"abaab"$的圖！

為了確定你的理解是對的，請自己動手畫出$"aaaa"$的圖
它應該長這個樣子：

有趣的是，在後面再加一個$'b'$之後，會變成這個樣子：

可以觀察到一個有趣的現象：

不同於之前的節點們，$5$代表的字串集合全部都變成黑色的了！

如果還躍躍欲試，可以挑戰看看畫出$"abcaba"$的圖

它應該長這個樣子：

但是，真的每次都可以只用綠色的邊就能搞定嗎？
好像沒辦法耶

下一篇將討論$"abbbb"$怎麼建圖！