SA-IS法において各接尾辞のS-type, L-typeを線形時間で決められることの説明

SA-IS法が何か、とかそういう話は書かないです（詳しい記事が無限にあるので）。あくまで、S-TypeとL-Typeを線形時間で決める方法についてだけ書きます。

結論だけを簡潔に

前提

SA-IS法において、最初のステップとして長さ$N$の文字列$S$の全ての接尾辞を「1文字目からN+1文字目」¹、「2文字目からN+1文字目」……、「N文字目からN+1文字目」、「N+1文字目」と並べたときに、それぞれの接尾辞に対して S-Type か L-Typeかを判定するものがある²。
普通に前から決めていくと、長さ$N+1$の文字列と長さ$N$の文字列の辞書順の比較、長さ$N$の文字列と長さ$N-1$の文字列の辞書順の比較……となり、トータルで$O(N^2)$の計算量がかかる。ところが実は、$S$を後ろから走査することにより、S-TypeかL-Typeかを全体で$O(N)$で判定できる。
…ということが、あちこちのサイトで説明されているが、その理由を詳細に書いてくれているところが見つからなかった。

実装の結論

$S$の$i$文字目の文字を$s_i$、$S$の$i$文字目から末尾までの接尾辞を$S_{i}$と表記するとき、$S_{i}$がS-TypeかL-Typeかは次の法則に従って決める。但し、後ろから走査するという前提があるので、$S_{i+1}$のTypeは既に決まっているとする。また、最後の接尾辞、つまり後ろから走査するとき一番最初に見ることとなる接尾辞のタイプはS-Typeとする。

• $s_i > s_{i+1}$のときは L-Type
• $s_i < s_{i+1}$のときは S-Type
• $s_i = s_{i+1}$のときは、$S_{i+1}$と同じType

$s_i \neq s_{i+1}$の場合は自明³で、等しい場合について以下説明する。

辞書順の定義から、1文字目が等しければ、2文字目以降、2文字目の等しければ3文字目以降、と再帰的に辞書順を比較することになる。
そして、実はこの2文字目以降、3文字目以降の辞書順の比較は、 $S_{i+1}, S_{i+2}$のTypeを決めるときに行った比較そのものである。これは接尾辞配列の作り方から明らか。つまり、接尾辞の先頭$k$文字が等しくて$k+1$文字目で初めて異なるときには、$k+1$文字目の辞書順の比較結果がそのまま全体の比較結果になるわけだが、先頭の文字が同じなら直前のTypeを引き継ぐというルールによって、後ろから見ていったときにはじめて $k+1$ 文字目にあたる個所を比較したときの結果が、ずっと引き継がれていくということになる。
上記の理由から、このような実装をとることで、各接尾辞がS-TypeなのかL-Typeなのかは、トータル $O(N)$で決めることができる。

参考文献

• https://gist.github.com/tjkendev/99d7330fe5642004b68268b31ba38ad4
  このソースコードのコメント行を見て、ようやくTypeの決め方を理解した

注釈

1. 接尾辞配列を考えるときは、$S$の$N+1$文字目に番兵として$S$に出現するどんな文字よりも辞書順が小さい文字を置くため、長さ$N$の文字列なのに$N+1$文字目という表現が出てくる。 ↩

2. 本文のように接尾辞を並べたときに $i$番目の接尾辞を $S_i$と置いたとき、接尾辞$S_i$がS-Typeであることの定義は、辞書順で$S_i < S_{i+1}$ が成り立つことで、 L-Typeの定義は 辞書順で$S_i > S_{i+1}$ が成り立つことである。但し、番兵1文字からなる最後の接尾辞については次の接尾辞が存在しない。これについては常にS-Typeとする。 ↩

3. 辞書順の定義そのものなので。例えば a***** と b***** (は任意の文字列が適当に入ると思ってください) なら 1文字目を見るだけで a**** の方が b***** よりも辞書順で小さい。 ↩