文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。 今回はJavaでSuffix Trieを使った探索をしてみた。 トライ木とパトリシア 先にトライ木とパトリシアについて紹介。 今回Suffix Trieという構造を調べていると、同じような構造としてSuffix Treeというものが出てきて混乱した。よく調べてみると、Suffixの集合をトライ木という構造で実装したものがSuffix Trieで、パトリシアという構造で実装したものがSuffix Treeらしい。 トライ木はnodeを連結していって、その枝に1文字を割り当てて辿れるようにした構造。トライ木は枝に1文字しか割り当てない構