2016年2月28日 星期日

後綴自動機 (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|)$!!!)

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原