JOI 夏季セミナー 2020 (8/25 〜 8/28) の成果物です。
テキスト : 高速文字列解析の世界（著:岡野原大輔)
Induced Sorting と呼ばれるSuffix ArrayをO(N)で構築するアルゴリズムを実装しました 。
全文検索機能である occ , locate も実装しました。
(参考文献)
Suffix Arrayを用いたBWT変換/復元を実装しました。
Wavelet Matrixに使うためのBit Vectorを実装しました。
rank と quantile を実装しました 。
※今回は文字列解析なのでスタート地点を配列に保存していますが、数が大きい場合は連想配列に保存します。
FM-index を用いた高速な全文検索を実装しました。メモリ圧縮はまだしていません。
Suffix Array , BWT , Bit Vector , Wavelet Matrix::rank , FM-index : https://onlinejudge.u-aizu.ac.jp/status/users/define_AC/submissions/1/ALDS1_14_D/judge/4798949/C++14
Wavelet Matrix::quantile : https://judge.yosupo.jp/submission/20203
- SA-IS.pdf ... 夏季セミの発表スライド
- FMindex.pdf ... 学校のレポートスライド