SuffixArrayがどんなものかを考えてみる。

SuffixArrayという言葉を最近知ったのだが、それが意味するところはいまいち分かっていない。
とりあえず、現状の認識としては以下のような感じ。※間違っている可能性が大いにあり

実際にどんなものなのかはそのうちに調べるとして、上の用件を満たすものの実現方法を思いついたのでメモしておく。

SuffixArray(仮)実装方法案

  1. TAIL配列に(検索対象となる)文字列(以後textと表記)を全てコピーする。
  2. textの先頭から順に(末尾までの部分文字列を)DoubleArrayに挿入していく。(text[0..text.len]、text[1..text.len]、...、text[text.len-1..text.len])
    1. 挿入処理は基本的に通常のDoubleArrayのそれと変わらないが、TAIL配列にキーの接尾文字列を追加する必要はなく、(TAIL配列に既にコピーされている)text内の該当する位置をBASE配列に設定すればいい。
  3. 検索方法は、DoubleArrayと変わらない。

以上。
話としては簡単で、DoubleArrayのTAIL配列の扱いを少し変えれば、SuffixArrayになるのではないか、ということ。
ちゃんと調べる前に、一回実装してみたい。