[SPOJ DQUERY][BIT][Persistent Segment Tree] D-query

原題連結
這題如果沒有想到一個關鍵點的話就會很難做

[SPOJ SUBLEX][Suffix Automaton] SUBLEX - Lexicographical Substring Search

題目連結

撇去Suffix Automaton的部份不談，這題有很多細節值得仔細探討

[SPOJ NSUBSTR][Suffix Automaton] NSUBSTR - Substrings

題目連結

恩....一樣是個只給O(n)方法過的字串題，倍增算法之類的只能吃土了QQ
後綴自動機的介紹請參考 這裡

[SPOJ LCS2][Suffix Automaton] LCS2 - Longest Common Substring II

題目連結

跟 LCS 這篇的作法非常相似，基本概念就不說了
不過寫這題的時候花了頗大量的時間釐清答案的更新順序和debug(最後的bug竟然是錯在toposort寫爛了...)

難點在於要怎麼兩兩合併計算答案，這要對後綴自動機上的狀態表示感受到一定深度才能體會(?
code中的許多assert可以幫助理解一些關鍵點和常有的bug

[SPOJ LCS][Suffix Automaton] LCS - Longest Common Substring

原題連結

Suffix Automaton(後綴自動機)的初級練習題，關於Suffix Automaton的教學和介紹網路上有很多資源，我之後也會自己補上一篇的
這題會用SAM的主要原因是SPOJ會莫名的把O(nlogn)的Suffix Array解卡掉，所以能過的大概只有後綴自動機或是O(n)後綴樹、後綴陣列的構造法吧