トライ木(Trie)
説明
プレフィックス木とも呼ばれる。あるノードの配下の全てのノードには自身に対応する文字列に共通するプレフィックスがあり, ルートには空の文字列が対応している。
使い方
- $\mathrm{add}(str, id)$: 添字が $id$ の文字列 $str$ をTrieに追加する。
計算量
追加 $O(|m|)$
$m$: 追加する文字列
実装例
Aho-corasick に継承させたいので, そういう実装になってます。
応用 1: 2 進数
Trie は xor と相性が良い。以下では, トライ木に格納されている値全体に対する xor と, max, min, mex クエリを実装している。
応用 2: パトリシア木
特に, トライ木で子ノードが $1$ つしかないノードを子ノードとマージして縮約した木をパトリシア木(または基数木) と呼ぶ。無駄な探索を減らすことが出来る。