辞書順に加えて文字の型も考慮する。同じ位置に同じ文字があるとき、それがS型の方がL型よりも小さいとするのが自然。S'[j'..n']。\big|S'[i']\big|=\big|S'[j']\big|のとき、S'[i'+1]とS'[j'+1]を比較すればよい。\big|S'[i']\big|<\big|S'[j']\big|のとき、S'[i']の末尾がS型なので、\big|S'[i']\big|文字目までに大小関係が確定する。sortを行うと、LMS部分文字列がソートされる。LMS型接尾字は頭文字についてのみソートされる。sortにより、各接尾辞の頭文字から2文字目以降で最初のLMS型の文字までソートされる。これはLMS部分文字列を含んでいる。補題5より、LMS部分文字列が相異なる場合、LMS部分文字列をソートすることとLMS型接尾辞をソートすることが同値であることが分かりました。同じLMS部分文字列が複数回登場する場合、定義4からそれらの正しい順序を決めることはできません。SA-ISを再帰的に適用することで、S'を正しくソートできる。n/2\rceilより、再帰は停止する。SA-ISにより、線形時間で接尾辞配列を構築できる。補題7より再帰全体の最悪計算量はn+n'+n''+\cdots=n+n/2+n/4+\cdots<2n。実装例Rust言語による番兵を用いない実装です。max_letterは登場する文字のうち最大のものを指します。これはバケットの両端を計算するために必要です。n/2\rceil種類あるためこのような実装になっています。実際に使用する場合、strを文字コードなどの「文字の大小関係を維持したユニークなインデックスの列」として与える必要があります。最大のインデックスがmax_letter[5][6]です。座標圧縮されている文字列の場合。\Sigma)で計算しても良い。S-type(もっとも左のS型)の略。S型のかたまりの左端。0x10FFFFとすればUnicodeで表現できるすべての文字に対応できます。u8::MAX)でよいでしょう。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。