aho_corasick

template <int char_size, int base>
struct aho_corasick;

概要

Aho Corasick法

名前	説明	計算量
`(constructor)`	根だけを持つ空のautomatonを構築する	$O(char\_size)$

名前	説明	計算量
`size`	ノード数を返す	$O(1)$
`failure`	ノードkのfailure linkを返す	$O(1)$
`failures`	failure link配列をコピーして返す	$O(S)$
`build`	failure linkを構築しBFS順のノード列を返す	$O(S(char\_size+D))$
`insert`	wordをtrieへ追加し各prefixのノードIDを返す	word長を $m$ として $O(m\cdot char\_size)$
`search`	(1) 状態nowから文字cを読んだ遷移先を返す (2) 状態nowから文字列strを読んだ各状態を返す	(1) 最大深さを $D$ として $O(D)$ (2) 文字列長を $n$、最大深さを $D$ として $O(nD)$
`get_node`	node_idのノードをコピーして返す	$O(char\_size)$

名前	説明	計算量
`node_type`	trieノード型	型エイリアスで実行時計算量はない

// (1)
int search(const char c, int now = 0);

// (2)
std::vector<int> search(const std::string &str, int now = 0);

(1) 状態nowから文字cを読んだ遷移先を返す

(2) 状態nowから文字列strを読んだ各状態を返す