LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-ZweiSuffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
