string_suffix_automaton

template <int ALPHABET_SIZE = 26, char BASE = 'a'>
struct string_suffix_automaton;

概要

固定alphabet向けSuffix Automaton

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

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

名前	説明	計算量
`node`	固定alphabet automatonの1状態	構築は $O(ALPHABET_SIZE)$

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

// (1)
string_suffix_automaton();

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

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

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

struct node;

固定alphabet automatonの1状態