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

全文検索
Suffix Array
Top / Suffix Array

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]

とすれば参照できる

検索