PythonでSuffixArray
def makeSuffixArray(s):
result = range(len(s))
result.sort(lambda x,y: cmp(s[x:], s[y:]))
for item in result:
print item, s[item:]
makeSuffixArray("abracadabra")
10 a
7 abra
0 abracadabra
3 acadabra
5 adabra
8 bra
1 bracadabra
4 cadabra
6 dabra
9 ra
2 racadabra
手抜きをするとこんなに行数が短くて驚きました。 もちろんsortの比較部分で毎回部分文字列を作っているので、これをこのまま巨大な文字列に使っちゃダメですけど、試しに実データで走らせてみると 100文字で1ミリ秒、300文字で8ミリ秒、1000文字で64ミリ秒だったので、僕の今回の目的にはこれで十分でした。 データが10倍になると実行時間が64倍になっているので、1万文字で4秒、10万文字で4分、100万文字で4時間、くらいは最低でもかかると覚悟して使ってください。
