接尾辞オートマトン（せつびじオートマトン、suffix automaton）や有向非巡回文字列グラフ（ゆうこうひじゅんかいもじれつグラフ、directed acyclic word graph）とは、接尾辞を効率的に表現するデータ構造。接尾辞木や接尾辞配列と同様に、suffix という文字列に対して構築した場合、suffix, uffix, ffix, fix, ix, x が含まれている事、それ以外が含まれていない事が分かる。文字列の集合 U の接尾辞オートマトンは、Q を U を表現するトライ木のノードすると、最大 2Q - 2 個の状態がある。接尾辞......
接尾辞オートマトン（せつびじオートマトン、suffix automaton）や有向非巡回文字列グラフ（ゆうこうひじゅんかいもじれつグラフ、directed acyclic word graph）とは、接尾辞を効率的に表現するデータ構造。接尾辞木や接尾辞配列と同様に、suffix という文字列に対して構築した場合、suffix, uffix, ffix, fix, ix, x が含......
