岡野原さんによる定数時間検索の解説

http://hillbig.cocolog-nifty.com/do/files/2005-12-compind.pdf
Suffix Array を使うと、
4NのメモリとO(log N)の時間で検索ができる
…というのはもう古い。

メモリはCSAでN/2程度、
時間はwavelet tree でO(m)