shiba_yu36 https://blog.hatena.ne.jp/shiba_yu36/ $shibayu36->blog; https://blog.shibayu36.org/ tech algorithm 文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。今回はJavaでSuffix Trieを使った探索をしてみた。 トライ木とパトリシア 先にトライ木とパトリシアについて紹介。今回Suffix Trieという構造を調べていると、同じような構造としてSuffix Treeというものが出てきて混乱した。よく調べてみると、Suffixの集合をトライ木という構造で実装したものがSuffix Tri… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.shibayu36.org%2Fentry%2F2017%2F01%2F08%2F223716" title="Suffix Trieを使って文字列マッチングする - $shibayu36-&gt;blog;" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/t/tanishiking24/20161218/20161218022331.png Hatena Blog https://hatena.blog 2017-01-08 22:37:16 rich https://blog.shibayu36.org/entry/2017/01/08/223716 1.0 100%