PalindromicTree

struct PalindromicTree;

概要

回文木 (eertree)

名前	説明	計算量
`(constructor)`	2つの根だけを持つ空の回文木を構築する	$O(1)$

名前	説明	計算量
`size`	ノード数を返す	$O(1)$
`get_active_idx`	現在の最長回文接尾辞ノードIDを返す	$O(1)$
`get_node`	idのノードへのpointerを返す	$O(1)$
`suffix_nodes`	各addで確定した最長回文接尾辞ノード列を返す	$O(1)$
`add`	末尾にchを追加し最長回文接尾辞ノードIDを返す	償却 $O(\log\sigma)$
`move`	既存木上でchを読んだ最長回文接尾辞へ移動する	最悪 $O(n\log\sigma)$
`build_frequency`	各相異なる回文の出現回数を返す	ノード数を $S$ として $O(S)$
`min_factorization`	各prefixの最小回文分割数を返す	$O(n\log n)$
`count_factorization`	各prefixの回文分割方法数を返す	$O(n\log n)$
`clear`	追加文字列とactive状態を空へ戻し、構築済みノードは保持する	$O(n)$

名前	説明	計算量
`node_type`	回文ノード型	型エイリアスで実行時計算量はない
`node_pointer`	回文ノードへのpointer型	型エイリアスで実行時計算量はない

template <class T>
std::vector<T> count_factorization();

各prefixの回文分割方法数を返す