Day 012-Q1 | 高度文字列（SA-IS / Z-algorithm）

問題

文字列 S が与えられる。S の各接尾辞（suffix）を辞書順にソートしたとき、辞書順で k 番目の接尾辞の開始インデックス（0-indexed）を答えよ。

入力形式

S
k

制約

$1 \le |S| \le 2 \times 10^5$

$S$ は小文字英字のみ

$1 \le k \le |S|$

入出力例

入力例 1

banana
3

出力例 1

入力例 2

abcabc
4

出力例 2

"banana" の接尾辞辞書順: a(5), ana(3), anana(1), banana(0), na(4), nana(2)。3番目は ana → index 3。

ヒント (段階的開示)

ヒント1: 方向性

接尾辞配列（Suffix Array）を構築する問題。SA[i] = 辞書順 i 番目の接尾辞の開始インデックス。

ヒント2: アプローチ

O(n log^2 n): 倍加法（Doubling）／O(n log n): DC3 / SA-IS。Z-algorithm は LCP 計算用の別アルゴリズム。

ヒント3: 誘導

def build_suffix_array(s):
    n = len(s)
    rank = [ord(c) for c in s]
    sa = list(range(n))
    k = 1
    while k < n:
        def cmp_key(i):
            r2 = rank[i + k] if i + k < n else -1
            return (rank[i], r2)
        sa.sort(key=cmp_key)
        # rank 再付与
        ...
        k *= 2
    return sa

模範解答 (Python)

import sys
input = sys.stdin.readline

def build_suffix_array(s):
    n = len(s)
    rank = [ord(c) for c in s]
    sa = list(range(n))
    k = 1
    while k < n:
        def cmp_key(i, k=k, rank=rank, n=n):
            r2 = rank[i + k] if i + k < n else -1
            return (rank[i], r2)
        sa.sort(key=cmp_key)
        tmp = [0] * n
        for j in range(1, n):
            tmp[sa[j]] = tmp[sa[j-1]]
            if cmp_key(sa[j]) != cmp_key(sa[j-1]):
                tmp[sa[j]] += 1
        rank = tmp
        if rank[sa[n-1]] == n - 1:
            break
        k *= 2
    return sa

S = input().strip()
k = int(input().strip())
sa = build_suffix_array(S)
print(sa[k - 1])

Step-by-Step 解説

1Suffix Array の定義
sa[i] = 辞書順 i 番目の接尾辞の開始位置。長さ n の文字列に対して n 個。

2倍加法
最初は各文字の ASCII を rank。毎ステップで比較長を 2 倍に。O(log n) × O(n log n) = O(n log^2 n)。

3順位の更新
同じ (rank[i], rank[i+k]) は同じ rank に。全 rank 異なれば early exit。

4k 番目の答え
sa[k-1]。

よくあるミス

ミス	原因	正しい書き方
`k` ループ変数でクロージャバグ	Python late binding	`def cmp_key(i, k=k, ...)`
early exit 条件忘れ	不要なイテレーション	`rank[sa[n-1]] == n-1`
接尾辞数を n-1 と誤認	off-by-one	長さ n には n 個

Day 012-Q1 — 高度文字列（SA-IS / Z-algorithm）

問題