2021-01-01から1年間の記事一覧

Suffix Automaton

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