有哪些後綴自動機的教程？

01-08

請問有沒有比較好的關於後綴自動機的教程？
順便請教一下後綴自動機與後綴數組、後綴樹有什麼區別與聯繫？如果能附上完整實現就更好了，謝謝!

最近我寫了一篇 SAM 的教程, Suffix Automaton Tutorial, 估計是目前最好的中文教程了 (光速逃

後綴自動機與線性構造後綴樹

范爺的博客，我覺得講的還是挺清楚的。

2012年noi冬令營陳立傑講稿

陳老師noi的講稿也是不錯的，其中有非常簡短的後綴自動機的代碼實現。

在cf上流傳的比較廣的一個教程是MAXimal :: algo :: Суффиксный автомат. Построение и применения

並且裡面有一個實現, 個人感覺後綴自動機看懂了理論實現起來應該是非常簡單的.

不過這個是俄文的, 用google翻譯翻成英文再加上自己腦補看懂問題不大, 裡面關於支撐後綴自動機的理論, 比如狀態代表等價類, 後綴link之類的都說的挺不錯的, 對於弄明白SAM非常有幫助.

SUFFIX AUTOMATON by- saisumit

這個大概是上面教程的英文版, 可能需要自帶梯子, 理論的東西可能少一些, 有一些簡單的例子.

評論里有大神說還有這個： http://www.codeforces.com/blog/entry/20861

題主也可以參考一下

可以先學學NFA（不確定有限自動機），再看看它怎麼轉化成DFA（確定型有限自動機）的，可能會對你理解後綴自動機有幫助

還有就是自己多用筆畫畫

可以看看

cly的ppt

fhq的博客

編譯原理前兩章

hihocoder上的後綴自動機系列

hihoCoder 後綴自動機一~六

陳立傑的WC課件

董克凡的講課課件

lazycal的博文

最近也在學這個，http://wk.baidu.com/view/e3b57f314431b90d6c85c7d5#1

覺得這篇文章還不錯，閱讀不需要太多前置技能。