最終更新:2008-10-17 (金) 07:35:43 (5664d)
Suffix Array
Top / Suffix Array
http://nais.to/~yto/doc/pub/dron-sa.pdf
Suffixとはテキスト中のある位置からテキスト末尾までの文字列のことで、”ある位置”をインデックスポイントと呼び、インデックスポイントの配列をSuffixの辞書順にソートしたもの。
単にインデックスになる単語の開始位置を格納した配列になる。
0 abracadabra 1 bracadabra 2 racadabra 3 acadabra 4 cadabra 5 adabra 6 dabra 7 abra 8 bra 9 ra 10 a
↓辞書順にソート
10 a 7 abra 0 abracadabra 3 acadabra 5 adabra 8 bra 1 bracadabra 4 cadabra 6 dabra 9 ra 2 racadabra
Suffix の3文字目を参照するならば、
buf[A[i] + 3]
とすれば参照できる