[TIOJ 1725][Z algorithm] Massacre at Camp Happy

原題連結
先了解一個問題：給定字串A,B，長度皆為n，要如何線性判定A和B是否只差1個字元呢？

[TIOJ 1735] k-口吃子字串

原題連結
嗚姆....這題還算基本的趣題，我想到兩個作法。

[POI XIII Stage 1][KMP] Periods of Words

原題連結
字串的一題基礎題

[POJ 2778][AC 自動機] DNA Sequence

原題連結

[Uva 1449][AC自動機] Dominating Patterns

原題連結
給出字串集合A和字串B，請找出A中出現在B最多次的字串，如果次數相同則按照出現順序輸出。

[教學][String][Data Structure] 後綴自動機(Suffix Automaton)

==========!! Warning !!==========
此文內容皆是出自自己的理解，若有與實際情況不符之處，請以論文或是大神文章為主
==========!! Warning !!==========

後綴自動機(Suffix Automaton)大概是我見過網路上最多教學資源的資料結構了，許多大陸和外國的神人都有寫教學文，包括寫過持久化資料結構介紹的clj大神。
不過有鑒於許多教學不是為了力求邏輯通順，定義複雜繁瑣，就是講解過程中，省略許多思考步驟，導致讀起來不甚順暢。
最後我還是決定自己完整的給出一篇教學文，使用最少的定義(3個)，盡量簡化構造它和使用它的思考流程，對於重要的性質除非必須，否則說明點到即止，不加以證明。

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

題目連結

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

[Codeforces Round #146 (Div. 1)] Cyclical Quest

題目連結

題目要求在一給定字串S上求出某一字串T的所有循環字串出現幾次
(此處循環字串的意義詳見原題)

[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)後綴樹、後綴陣列的構造法吧

[Codeforces 452E][MemSQL Start[c]UP 2.0 - Round 1][Suffix Array] Three strings

原題連結

首先老規矩，把三個字串用神秘的符號分隔後拼接起來，構造SuffixArray和Height陣列

相似的後綴會被排在一起，而且我們可以很快知道在SuffixArray的一群連續後綴的LCP(by H陣列)