Trie と文字列探索 (Aho-Corasick)

Trie (トライ木)

接頭辞 (prefix) を共有して文字列集合を格納する木。「重複する部分列を共有する」という発想で、辞書引きや前方一致検索を高速に行える。多くの文字列アルゴリズムの土台となる。

Aho-Corasick

複数のパターン文字列を入力テキストから一括かつ高速に探索するアルゴリズム。計算量 $\mathcal{O}(N+M)$。

• Trie を構築し、各ノード（例: abc）からその最長 suffix を表すノード（bc → c → root）へ failure link を張る
• マッチに失敗したときこのリンクを辿ることでバックトラックなしに探索を継続できる

関連: ハッシュ

• Zobrist hashing — 集合や盤面状態をハッシュ化する手法。要素ごとに乱数を割り当て XOR で集約することで、増減を差分更新できる。ゲーム木探索の局面ハッシュなどで使う。

関連: balanced-search-tree / game-tree-search / _moc-algorithm