SA-IS

2段階ソートでは Suffix を L-type と S-type の2種類に分類することで高速化を図りました． しかし，結局 S-type のソートを行わなれけばならないという問題点がありました． この S-type のソートも線形時間で行なってしまうのが SA-ISです．

Left-most-S(LMS)

2段階ソートではすべての S-type Suffix をソートしたわけですが， L-type をソートするためだけだったら，すべてをソートする必要はありません． S_iの情報を使ってS_i-1の位置を決めているので， 「S_i-1が L-type である S-type の Suffix S_i」 だけソートできていればいいはずです． このような Suffix を LMS と呼びます． 「abracadabra$」の場合は Suffix は以下のようになり，表で色をつけた Suffix が LMS となります．

No.	開始位置	Suffix	タイプ
0	0	abracadabra$	S
1	1	bracadabra$	S
2	2	racadabra$	L
3	3	acadabra$	S
4	4	cadabra$	L
5	5	adabra$	S
6	6	dabra$	L
7	7	abra$	S
8	8	bra$	S
9	9	ra$	L
10	10	a$	L
11	11	$	S

Induced Sorting

この LMS をソートしバケットに分類して Suffix Array の表に入れます． このとき LMS は 各バケットの下の方に詰めます． (LMSでない S-type を考慮してないので，Suffix Array が完成したときのLMSの位置とは異なることに注意してください． しかし，「LMS の出現順」さえ合っていれば L-type の位置を決定することができるので，今は気にしない事にします． 具体的な S-type の位置はまたあとで求めます．)

No.	開始位置	Suffix	タイプ
0	11	$	S
5			L
2			S
3	7	abra$	S
4	3	acadabra$	S
5	5	adabra$	S
6			S
7	8	bra$	S
8			L
9			L
10			L
11			L

L-type の位置を決定する手順は2段階ソートと全く同じです． 「上から順番にSuffix S_iを検索」「S_i-1がL-typeならバケットの一番上の空きに挿入」 という手順で求めることができます．

No.	開始位置	Suffix	タイプ
0	11	$	S
5	10	a$	L
2			S
3	7	abra$	S
4	3	acadabra$	S
5	5	adabra$	S
6			S
7	8	bra$	S
8	4	cadabra$	L
9	6	dabra$	L
10	2	racadabra$	L
11	9	ra$	L

これで L-type の位置が求まりました． 次に S-type の位置を求めるのですが，実は L-type と走査方向が違うだけでほとんど同じ方法で求めることができます． 上から検索，上の空きに挿入だったのを， 「下から順番にSuffix S_iを検索」「S_i-1がL-typeならバケットの一番下の空きに挿入」 とするだけです(ただし，前の操作で入れたLMSは無視する)． こうなる理由は L-type の時と不等号の向きを反対にすればわかると思います．

ここまでで，ソート済みのLMSを使って「L-type の位置を求める，L-type の位置から S-type の位置を求める」という手順で Suffix Array が求まることが分かりました． この手順を Induced Sorting と呼びます．

LMS-substring

Induced Sorting で Suffix Array が求まることが分かりましたが， 依然として「LMSをソートする」という問題が残っています． これを何とかすることを考えましょう．

LMSから次のLMSまでの部分文字列を LMS-substring と呼びます． 「abracadabra$」の場合，3・5・7・11文字目から始まる Suffix が LMS なので， 3〜5(aca)，5〜7(ada)，7〜11文字目(abra$)が LMS-substring です． 終端文字の「$」は厳密にはこの定義に当てはまりませんが，便宜上 LMS-substring 扱いしておきます．

• abracadabra$
• abracadabra$
• abracadabra$
• abracadabra$

LMS-substring に小さいものから順番に番号を振っていきます．

0. $
1. abra$
2. aca
3. ada

ここでつけた番号を LMS-substring を出現順に並べます． 例の場合は「aca」 「ada」「abra$」「$」の順番で出現しているので， 「2310」となります．

この「2310」という文字列に対して Suffix Array を構築してみましょう．

No.	開始位置	Suffix	LMS-substring	LMS
0	3	0	$	S11
0	2	10	abra$$	S7
0	0	2310	acaadaabra$$	S3
0	1	310	adaabra$$	S5

ここで0から3までの数字が，もともと LMS-substring であったことを思い出すと， 「2310」の Suffix は元の文字列の LMS Suffix と 1対1 に対応しており， さらにその大小関係が変わっていないことが分かります． つまり「元文字列の LMS をソートする」ことと「LMS-substring列の Suffix Array を構築する」ことは全く同じことをしていることになります．

LMS-substringをソートする

「LMS をソート」と「LMS-substring 列の Suffix Array の構築」が同じであることが分かりました． ここまで来ればあともう一歩． 最後に残った問題は 「LMS-substring をソートし，小さいものから順番に番号をつける」ことです．

もう一度，Induced Sorting について考えてみましょう． 一番はじめのステップで「LMSをソートする」必要がありますがこれは大変です． しかし，「LMSを『先頭の文字について』ソートする」のであれば バケットソートを使って簡単に実行できます． そこで，少し妥協して，LMSを「先頭の文字についてソート」したのち，Induced Sorting を適用してみます．

No.	開始位置	Suffix	タイプ
0	11	$	S
1			L
2			S
3	7	abra$	S
4	5	adabra$	S
5	3	acadabra$	S
6			S
7			S
8			L
9			L
10			L
11			L

Suffix の赤字になっている部分でソートしました． 各バケットでLMSの開始位置が逆順になっていることに注意してください． この状態からInduced Sorting を実行してみます．

No.	開始位置	Suffix	タイプ
0	11	$	S
1	10	a$	L
2	7	abra$	S
3	0	abracadabra$	S
4	3	acadabra$	S
5	5	adabra$	S
6	8	bra$	S
7	1	bracadabra$	S
8	4	cadabra$	L
9	6	dabra$	L
10	9	ra$	L
11	2	racadabra$	L

「S_iが先頭 n 文字についてソートされていれば，S_i-1は 先頭 n + 1 文字ソートされた位置に挿入される」ので， Induced Sort の結果は赤字で示した部分についてソートされます． ここで，LMS であった S₃, S₅, S₇, S₁₁ に着目してみましょう． それぞれ「aca」「ada」「abra$」「$」についてソートされています．

この文字列，どこかで見ましたね？ そう，LMS-substringです！ つまり，「LMSの先頭1文字についてソートし Induced Sort を行う」と LMS-substring のソートができるのです．

まとめ

ここまでのことを整理すると，以下の手順で Suffix Array を求めることができます．

1. LMS-substring のソートを行う
   1. LMS の先頭1文字についてソートを行う
   2. Induced Sort を行う
2. LMSのソートを行う
   1. LMS-substring に小さいものから順位付け
   2. 順位を LMS-substring の出現順に並べる
   3. 新たにできた文字列について Suffix Array を求める(Suffix Array を求める手順を再帰的に適用する)
3. Induced Sort により Suffix Array を完成させる

それぞれの手順は，入力の長さについて線形時間で求まります． 途中LMS-substring列のSuffix Array を再起的に求める必要がありますが， この長さは元文字列の半分以下です． そのため線形時間で Suffix Array が構築できることが保証されています．