(Copyright：圖片轉載請註明來源網址，感謝～)
我們已經在紙上演練了這麼多次，該來看看這個很視覺化的東西要怎麼用程式來實作了吧？
首先是節點儲存問題
回顧定義，每個節點都代表了一個字串的一堆後綴所組成的字串集合
例如這張$S="abbbb"$圖：(還記得$S$是甚麼嗎？趕快到這裡複習一下吧～)
可以發現節點$7$代表了$"abbbb"$、$"bbbb"$、$"bbb"$、$"bb"$、$"b"$這些字串，也就是$"abbbb"$的所有後綴組成的字串集合
可是又不能很貪心地只儲存長度最長的$"abbbb"$，因為這些字串還有黑色和綠色之分，是會影響下一次加入新字母時的行為的......咦？真的是這樣嗎？
可以發現，$7$的綠色邊指向$8$，而$8$所代表的字串集合 (分別是$"bbb"$、$"bb"$和$"b"$) 恰好就是$7$的所有綠色字串！
廢話，不然要綠色邊的作用是啥？(該不會真的忘記綠色邊是幹嘛的吧？請從這裡找到它的定義吧～)
不用另外存$7$所代表的每個字串的顏色了
因此，對於$7$這個節點，我們真的只要儲存長度最長的$"abbbb"$就好了！
可是這樣每個節點還是需要$O(\left|S\right|)$的空間來儲存QQ
仔細觀察一下，如果我們只知道圖的形狀和每條邊代表的字母，能不能推出任意節點代表的字串集合中最長的那一個字串 (因為其他的字串枚舉後綴就出來了) 呢？
其實，如果真的需要這些資訊的話，我們只要把$0$、$1$、$2$、$3$、$5$、$7$特別標記起來
然後對於每個節點$u$，存下其代表的字串集合中最長字串的長度 (稱作$max\_len[u]$吧) 就好了
這樣一來
假如我要知道$5$代表的最長字串長怎樣：
因為$5$被特別標記起來了，因此可以直接知道答案是$S$的前$max\_len[5]=4$個字母組成的字串 (求得$"abbb"$)
假如我要知道$8$代表的最長字串長怎樣：
隨便挑一條「指向$8$」的綠色邊「反向」走到另一個節點$u$，遞迴得到$u$的答案為$s$ (如果走到$5$，$s="abbb"$；如果走到$7$，$s="abbbb"$)，那麼$8$代表的最長字串就是$s$的後$max\_len[8]=3$個字母組成的字串了 (求得$"bbb"$)
所以每個節點只要存兩個資訊就好：有沒有被特別標記、其代表的字串集合中最長字串的長度！
現在，我們儲存「點」的空間複雜度已經可以降到$O(\left|S\right|)$了
那麼，儲存「邊」的空間複雜度呢？
最主要的節點儲存問題已經解決了，還是趕快來寫code比較重要吧 (好啦其實是因為用程式流程來講會比較好解釋)
下一篇將說明用程式實作$SAM$的方式 (其實這張圖就是後綴自動機 ($SAM$) 啦，沒有很困難的對吧(?) )
沒有留言:
張貼留言
歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。