suffix_automaton

template <class T = char>
struct suffix_automaton;

概要

Suffix Automaton

任意の比較可能な要素型に対し、部分文字列を受理する最小DFAをオンライン構築する。固定英字向けには string_suffix_automaton を利用できる。

長さnの構築は suffix_automaton<T> が $O(n\log\sigma)$、 string_suffix_automaton が $O(n)$。状態数は $O(n)$

名前	説明	計算量
`(constructor)`	(1) 初期状態だけを持つautomatonを構築する (2) 列sからautomatonを構築する	(1) $O(1)$ (2) $O(n\log\sigma)$

名前	説明	計算量
`extend`	末尾に文字cを追加する	償却 $O(\log\sigma)$
`next_state`	現在の照合状態へ文字cを追加した状態と一致長を返す	単発最悪 $O(n\log\sigma)$、文字列を順に処理する場合は償却 $O(\log\sigma)$
`size`	状態数を返す	$O(1)$

名前	説明	計算量
`node`	Suffix Automatonの1状態	状態の構築は $O(1)$

名前	説明	計算量
`nodes`	全状態	参照は $O(1)$
`last`	文字列全体に対応する末尾状態	参照は $O(1)$

// (1)
suffix_automaton();

// (2)
template <class Container>
explicit suffix_automaton(const Container &s);

(1) 初期状態だけを持つautomatonを構築する

(2) 列sからautomatonを構築する

struct node;

Suffix Automatonの1状態