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

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

說明：(這些是關於字串的基本用語，非常重要，請務必牢記)
「$\left|s\right|$」代表字串$s$的長度
「字串$s$的後綴」代表由$s$的最後幾個字母組成的字串，$s$有$\left|s\right|$個後綴
「字串$s$的子字串 (簡稱子串)」代表$s$中一段連續的字母組成的字串，$s$有$\frac{\left|s\right|(\left|s\right|+1)}{2}$個子字串 (不計較重複的話)


假如我給你一個字串$S$，然後問你很多次一個字串$A_{i}$是不是$S$的子字串 (全部由小寫字母組成)
我們能不能對$S$做個預處理，然後$O(\left|A_{i}\right|)$回答每個詢問呢？

我們先來看一種$O(\left|S\right|^{2})$的預處理
我們可以先將$S$的所有後綴建成一棵樹
假設$S="abcd"$，那麼樹就長成這個樣子：

其中$0$是根，每條邊都有代表的字母
這樣的話，假如我問你$"bc"$是不是子字串
那就從$0$依序嘗試沿著代表字母$b$、$c$的邊走
於是，我們會經過$0$、$5$、$6$，最後停在$6$
走完了，因此$"bc"$是$S$的子字串！

如果問你$bca$呢？
那就從$0$依序嘗試沿著代表字母$b$、$c$、$a$的邊走
於是，我們會經過$0$、$5$、$6$
可是$6$後面沒有代表字母是$a$的邊 (只有$d$)，所以走不下去惹QQ
因此$"bca"$不是$S$的子字串！

如果$S="abccba"$，那麼樹就長成這個樣子：

以下是$S$的所有子字串依照上述方式走最後會停在哪個節點
$"a"\rightarrow 1$
$"ab"\rightarrow 2$
$"abc"\rightarrow 3$

$"abcc"\rightarrow 4$

$"abccb"\rightarrow 5$

$"abccba"\rightarrow 6$

$"b"\rightarrow 7$
$"bc"\rightarrow 8$

$"bcc"\rightarrow 9$

$"bccb"\rightarrow 10$

$"bccba"\rightarrow 11$

$"c"\rightarrow 12$

$"cc"\rightarrow 13$

$"ccb"\rightarrow 14$

$"ccba"\rightarrow 15$

$"c"\rightarrow 12$

$"cb"\rightarrow 16$

$"cba"\rightarrow 17$

$"b"\rightarrow 7$

$"ba"\rightarrow 18$

$"a"\rightarrow 1$

可以自己試著走走看哦^_^

這樣預處理的時間複雜度是$O(\left|S\right|^{2})$，空間複雜度也是$O(\left|S\right|^{2})$

下一篇將介紹一種空間複雜度$O(\left|S\right|)$的方法 (最後會發現......竟然連時間複雜度都是$O(\left|S\right|)$！！！)