最終更新:2008-10-17 (金) 07:35:43 (4354d)  

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]

とすれば参照できる

http://homepage3.nifty.com/DO/suffix_array.htm