その他:Suffix Arrayについて

資料:http://www.hgc.jp/~tshibuya/classes/shibuya20040629.pdf
資料：http://sary.sourceforge.net/docs/suffix-array.html.ja
文字を接尾語で分割し、辞書順に並べることで検索したい文字を探すことを効率的に行える。

例:sakurasaku
1.sakurasaku
2.akurasaku
3.kurasaku
4.urasaku
5.rasaku
6.asaku
7.saku
8.aku
9.ku
10.u

これを辞書順に並べると
8.aku
2.akurasaku
6.asaku
9.ku
3.kurasaku
5.rasaku
7.saku
1.sakura
10.u
4.urasaku

となる。
ここで、「aku」という単語を検索した場合、indexの8と2に含まれていることがわかり、
２から８の間で2分探索する。
2
3
4
5←スタート
6
7
8
この仕組により、早く検索することができる