SA-ISとは

SA-ISは接尾辞配列を文字列長の線形時間で求めるアルゴリズム。
元論文：Two Efficient Algorithms for Linear Time Suffix
Array Construction [G Nong, et.al.]
以下個人的に悩んだところ。

LMS-substringのrename

ちょっとだけ悩んだ。
１回目のinduced sortingの後にLMS-substringがsortされていることを利用して辞書順で小さいLMS-substringから比較していけば良いだけだった。
renameで得られた新しいアルファベットでLMS-substringがuniqueかどうかの判定ができる。

$n$ を文字列長、$l$ をLMS-substringの数とする。
上のrename処理が辞書順に見ていくので適当に格納すると出現順が崩れて再帰する際の文字列が得られない。配列をもう一つ用意すれば簡単だがメモリ的にうれしくない。
うまくやるために、以下の性質を使う。
- $l$ は$\lfloor n/2 \rfloor$以下。
- LMS-characterの隣はLMS-characterにならない。
LMS-substringの辞書順が求まったら作業用配列の先頭に辞書順情報だけ格納して、それ以外の値を初期化する。
rename処理の中で、元の文字列での出現位置が$p$となるLMS-substringに対して、renameした値を作業用配列の($l$+$\lfloor p/2 \rfloor$)の位置に格納する。上記の性質から格納位置は被らないし溢れない。
配列の$l$ 以降で初期化されていない値は元の文字列の出現順にLMS-substringがrenameされた値となっているので、ここから新しい文字列を生成して再帰的にinduced sortする。

手法	実行時間
SA-IS	2.92 [s]
LS	14.74 [s]