概要 文字列 $S$ のSuffix Automatonとは、ざっくりいうととても性質のいいDFA(決定性オートマトン)である。一番代表的な性質は次のとおりである。 $S$ の部分文字列全て、またそれらのみを受理する。 頂点数，辺数が $O(|S|)$、より正確には $|V| \leq (2|S…