昔作った「Perlによるsuffix arrayの実装」を発掘したので公開しておき
ます。

ソースコードです。

#!/usr/bin/perl -w
use strict;
my $t = "mississippi";		# Text - 対象テキスト
my @sa = (0..length($t)-1);	# Suffix Array - 初期設定

### Suffix Array の作成
@sa = sort {substr($t, $a) cmp substr($t, $b)} @sa;
# テスト出力
for (0..$#sa) { print "$_ $sa[$_] ",substr($t, $sa[$_]),"\n"; }

### バイナリサーチによる Suffix Array の検索
my $k = "ppi";			# Key - 検索キー
my ($l, $u) = (0, $#sa);
while ($l <= $u) {
    my $i = int(($l + $u)/2);
    my $c = $k cmp substr($t, $sa[$i], length($k));
    if ($c > 0) {
        $l = $i + 1;
    } elsif ($c < 0) {
        $u = $i - 1;
    } else {
        print qq("$k" is found at $sa[$i]\n);
        last;
    }
}

実行結果です。

% perl sa.pl
0 10 i
1 7 ippi
2 4 issippi
3 1 ississippi
4 0 mississippi
5 9 pi
6 8 ppi
7 6 sippi
8 3 sissippi
9 5 ssippi
10 2 ssissippi
"ppi" is found at 8

Suffix Arrays については、[2006-04-10-3]にリンク集をまとめましたの
でどうぞ。


当時ネット上でsuffix arrayのPerl実装がどこかで公開されていたはずな
のですが、今検索すると見つけられません…。
見つけた方、ご存知の方はURLを教えてください。

追記060411: 見つかりました！ありがとうございます。
お手軽PerlでSuffixArrayに挑戦
http://www006.upp.so-net.ne.jp/ugougo/tech/lang_perl/easy_suffixarray.html