Day 137-Q2 | SA-IS法（Suffix Array Induced Sorting）

問題

英小文字のみからなる文字列 $S$（長さ $N$）が与えられる。$S$ の Suffix Array（すべての接尾辞を辞書順に並べたときの開始位置の列）を求めよ。

DC3法（Skew Algorithm、Day100-Q3）とは異なる、L/S型分類 + LMS（Left-Most S-type）部分文字列の誘導ソートによるアルゴリズム（SA-IS: Suffix Array by Induced Sorting）を用いて、真の線形時間 $O(N)$ で構築せよ。

入力形式

N
S

制約

$1 \le N \le 2\times10^5$

$S$ は英小文字のみ

入出力例

入力例1

6
banana

出力例1

5 3 1 0 4 2

入力例2

11
mississippi

出力例2

10 7 4 1 0 9 8 6 3 5 2

概念図

ヒント（段階的開示）

ヒント1（方向性）

ダブリング法で$O(N\log N)$、DC3法（Day100-Q3）で$O(N)$が達成できる。SA-ISは全く異なるアプローチで「各文字を2種類に分類し、その分類パターンだけから直接ソート済みの位置に配置（誘導）する」ことで線形時間を実現する。

ヒント2（アプローチ）

各位置$i$を「S型(suffix(i)<suffix(i+1))」か「L型(suffix(i)>suffix(i+1))」に分類（末尾はS型）。S型かつ直前がL型の位置をLMSと呼ぶ。LMSだけを大まかにバケツソートし、induce L→induce Sの2パスで正しい誘導を行う。LMS部分文字列に順位を付けて縮小文字列を作り、全て相異なれば直接、そうでなければ再帰する。

ヒント3（誘導）

def induce_sa(lms_positions):
    sa = [-1] * n
    buckets = get_buckets(True)
    for p in reversed(lms_positions):
        buckets[s[p]] -= 1
        sa[buckets[s[p]]] = p
    buckets = get_buckets(False)
    for i in range(n):
        j = sa[i] - 1
        if sa[i] > 0 and not t[j]:
            sa[buckets[s[j]]] = j
            buckets[s[j]] += 1
    buckets = get_buckets(True)
    for i in range(n - 1, -1, -1):
        j = sa[i] - 1
        if sa[i] > 0 and t[j]:
            buckets[s[j]] -= 1
            sa[buckets[s[j]]] = j
    return sa

末尾に他より小さい番兵($コード0)を付けてから処理すると境界処理が単純化される。

模範解答 (Python)

import sys
sys.setrecursionlimit(10000)


def sa_is(s, alphabet_size):
    n = len(s)
    if n == 0:
        return []
    if n == 1:
        return [0]

    t = [False] * n
    t[n - 1] = True
    for i in range(n - 2, -1, -1):
        if s[i] < s[i + 1]:
            t[i] = True
        elif s[i] > s[i + 1]:
            t[i] = False
        else:
            t[i] = t[i + 1]

    def is_lms(i):
        return i > 0 and t[i] and not t[i - 1]

    bucket_sizes = [0] * alphabet_size
    for c in s:
        bucket_sizes[c] += 1

    def get_buckets(end):
        buckets = [0] * alphabet_size
        total = 0
        for c in range(alphabet_size):
            total += bucket_sizes[c]
            buckets[c] = total if end else total - bucket_sizes[c]
        return buckets

    def induce_sa(lms_positions):
        sa = [-1] * n
        buckets = get_buckets(True)
        for p in reversed(lms_positions):
            buckets[s[p]] -= 1
            sa[buckets[s[p]]] = p
        buckets = get_buckets(False)
        for i in range(n):
            j = sa[i] - 1
            if sa[i] > 0 and not t[j]:
                sa[buckets[s[j]]] = j
                buckets[s[j]] += 1
        buckets = get_buckets(True)
        for i in range(n - 1, -1, -1):
            j = sa[i] - 1
            if sa[i] > 0 and t[j]:
                buckets[s[j]] -= 1
                sa[buckets[s[j]]] = j
        return sa

    lms_positions = [i for i in range(1, n) if is_lms(i)]
    sa = induce_sa(lms_positions)

    lms_names = [-1] * n
    name = 0
    prev = -1
    for p in sa:
        if is_lms(p):
            if prev == -1:
                lms_names[p] = name
            else:
                diff = False
                d = 0
                while True:
                    if s[prev + d] != s[p + d] or t[prev + d] != t[p + d]:
                        diff = True
                        break
                    if d > 0 and (is_lms(prev + d) or is_lms(p + d)):
                        break
                    d += 1
                if diff:
                    name += 1
                lms_names[p] = name
            prev = p

    reduced = [lms_names[p] for p in lms_positions]

    if name + 1 == len(lms_positions):
        reduced_sa = [0] * len(reduced)
        for i, v in enumerate(reduced):
            reduced_sa[v] = i
    else:
        reduced_sa = sa_is(reduced, name + 1)

    sorted_lms = [lms_positions[i] for i in reduced_sa]
    sa = induce_sa(sorted_lms)
    return sa


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    s_str = data[1].decode()

    rank = {c: i + 1 for i, c in enumerate(sorted(set(s_str)))}
    arr = [rank[c] for c in s_str] + [0]
    full_sa = sa_is(arr, len(rank) + 2)
    sa = full_sa[1:]

    print(" ".join(map(str, sa)))


main()

Step-by-Step 解説

1L/S型分類とLMS位置
末尾を強制的にS型とし、右から左へ「次の文字より小さければS型、大きければL型、同じなら次と同じ型」で分類。LMSはS型のかたまりの先頭にあたる位置。

2誘導ソートの3ステップ構造
LMSだけをバケツ末尾に大まかに配置し、「L型を左から右へ誘導」→「S型を右から左へ誘導」の2パスを行う。

3LMS部分文字列の命名と縮小文字列
2回の誘導でLMS部分文字列同士の相対順序が正しく確定する。ソート済みLMS列を走査し、隣接するLMS部分文字列が同じなら同じ番号、違えば新しい番号を振る。

4再帰と終了条件
縮小文字列が全て相異なる番号ならそのまま利用、重複があれば再帰。縮小文字列の長さは元の半分以下なので、全体で$T(N)=T(N/2)+O(N)=O(N)$。

5最終誘導とオフセット処理
正しい順序のLMS位置列を種にもう一度induce L→induce Sを行うと全体のSuffix Arrayが完成する。番兵を付けてから呼び、結果の先頭（番兵自身）を除く。

よくあるミス

ミス	原因	正しい書き方
LMS部分文字列の比較で範囲外参照	番兵を付けずに実装し比較ループが末尾を超える	末尾に他より小さい番兵（コード0）を必ず付加する
is_lms(0)をTrueにしてしまう	先頭位置は「直前」が存在しないのに判定してしまう	is_lmsの定義で i>0 を必ずチェックする
誘導のバケツ境界を使い回す	induce Lとinduce Sで異なる境界が必要なことを見落とす	get_buckets(False)とget_buckets(True)を用途ごとに呼び分ける
縮小文字列の再帰終了条件を誤る	「名前の最大値+1==LMSの個数」の判定を書き間違える	全LMSに相異なる名前が付いた場合のみ直接構築、それ以外は再帰
出力に番兵の接尾辞を含めてしまう	full_saをそのまま出力する	番兵の接尾辞は常にSA先頭に来るのでfull_sa[1:]で除く

次のステップ

発展: 得たSuffix ArrayからKasai法でLCP配列をO(N)構築し、区間RMQと組み合わせて任意の2接尾辞のLCEクエリにO(1)で答える構成（Day123-Q2）と接続せよ。
発展2: DC3法（Day100-Q3）と実行時間・実装量を比較し、それぞれの利点を実測で確認せよ。

自己評価

完全理解おおむね理解要復習

Day 137-Q2 — SA-IS法（Suffix Array Induced Sorting）

問題