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

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

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

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

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

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

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

$3$還差一個$"b"$就可以代表$"abb"$的所有後綴了
一樣的問題又來了，路徑$"b"$已經存在了，會連到$2$！
套用一樣的老方法，從$3$到$2$連一條綠色的邊：

額......好像出錯惹......
$2$代表的字串集合中有些不是$"abb"$的後綴啊QQ
既然我們需要一個代表$"b"$的節點，那就自己創造一個吧！
方法是從$2$分離出一個符合需求的點！

建立一個新節點$4$代表$"b"$

可是這樣就把$"b"$從$2$代表的字串集合搶走了
沒關係，從$2$到$4$連一條綠色邊，把丟掉的$"b"$加回來就沒事了

路徑$"bb"$之前是從$2$走到$3$的，現在要讓它改由從$4$走到$3$
像以前的$2$一樣，$4$要連邊$'b'$到$3$

現在，所有點代表的字串集合已經全部恢復原狀
除此之外，我們還多了一個代表$"b"$的點$4$！
這樣一來，我們就可以從$3$連一條綠色邊到$4$了
耶！

加入邊$′b′$，讓路徑$"abbb"$會走到新節點$5$，這時$5$代表了$"abbb"$和$"bbb"$ (因為是從$3$走過來的，因此代表了$"abb"$和$"bb"$再加一個$′b′$)：

$3$還差$"bb"$和$"b"$就可以代表$"abbb"$的所有後綴了
一樣的問題又來了，路徑$"bb"$已經存在了，會連到$3$！
套用一樣的老方法，從$5$到$3$連一條綠色的邊
然後一樣又因為$3$代表的字串集合中有些不是$"abbb"$的後綴而出錯
一樣又要把需要的點從$3$分離出來
建立一個新節點$6$代表$"bb"$和$"b"$

可是這樣就把$"bb"$從$3$代表的字串集合搶走了
沒關係，從$3$連出的綠色邊改成連到$6$，就可以把丟掉的$"bb"$加回來了

路徑$"bbb"$之前是從$3$走到$5$的，現在要讓它改由從$6$走到$5$
像以前的$3$一樣，$6$要連邊$'b'$到$5$

現在，所有點代表的字串集合已經全部恢復原狀
除此之外，我們還多了一個代表$"bb"$和$"b"$的點$6$！
這樣一來，我們就可以從$5$連一條綠色邊到$6$了
耶！

接下來就只附過程圖了 (一樣的概念)，打字好累Orz

於是，我們就把$"abbbb"$的圖建出來了！

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

如果還躍躍欲試，可以挑戰看看畫出$"abccba"$的圖
經過這一連串的過程：

最後應該長這個樣子XD：

但是，真的每次都可以只用綠邊和分離一個點就搞定嗎？
恭喜！答案是Yes (如果想知道為甚麼，請繼續看下去吧～)

咦？剛剛的建圖過程好像還滿有道理的
可是......知道了要怎麼用紙筆畫出任意字串的這種圖
你真的知道要怎麼用程式來儲存圖上的所有資訊嗎？

下一篇將教你如何有效的將圖上各種資訊儲存好！