SAIS論文を読了した。これは賢いなあと思った。ので概要だけ書いておく。 参考: SACAs(Suffix Array Construction Algorithms) 本手法ではLMS-substringという可変長の部分文字列を使って再帰的にsuffix arrayを構築する。再帰時に文字列長は最大でも1/2のサイズになるため高速な構築が期待できる。ただし構築に必要なメモリ空間は従来のsuffix arrayと変わらない。 まず文字列S(長さはn)のそれぞれの文字にSまたはLというフラグを立てる。直後の文字より小さければS、大きければL、同じならば同じフラグを付ける。文字列の末尾には$という記号がついていて、これはあらゆる文字より小さく、フラグはSとする。例えば abracadabra$ SSLSLSLSSLLSとなる。ここで直前の文字がLで、自分がSであるような文字をLMS-char