Day 058-Q1 — Suffix Array + Lyndon Factorization

問題

長さ $N$ の文字列 $S$ が与えられる。以下の $Q$ クエリを処理せよ。

• クエリ 1 l r: $S[l..r]$ を Lyndon 分解し、辞書順最大の Lyndon 語の長さと個数を出力せよ。
• クエリ 2 l r: $S[l..r]$ の辞書順最小回転の開始位置（0-indexed）を出力せよ。

入出力例

13 2
aababacabacab
1 1 7
2 1 7

2 1
3

$S[1..7]="aababac"$: Lyndon 分解を適用し最大 Lyndon 語を求める。
最小回転はBooth's algorithmで O(N) に解ける。

概念図: Lyndon 分解と最小回転

ヒント（段階的開示）

def lyndon_factorization(s):
    n, i = len(s), 0
    result = []
    while i < n:
        j, k = i, i + 1
        while k < n and s[j] <= s[k]:
            if s[j] < s[k]:
                j = i
            else:
                j += 1
            k += 1
        while i <= j:
            result.append(s[i:i + k - j])
            i += k - j
    return result

def min_rotation(s):
    s2 = s + s
    n = len(s)
    f = [-1] * (2 * n)
    k = 0
    for j in range(1, 2 * n):
        sj = s2[j]
        i = f[j - k - 1]
        while i != -1 and sj != s2[k + i + 1]:
            if sj < s2[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != s2[k + i + 1]:
            if sj < s2[k]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def lyndon_factorization(s):
    n, i = len(s), 0
    result = []
    while i < n:
        j, k = i, i + 1
        while k < n and s[j] <= s[k]:
            if s[j] < s[k]:
                j = i
            else:
                j += 1
            k += 1
        while i <= j:
            result.append(s[i:i + k - j])
            i += k - j
    return result

def min_rotation(s):
    s2 = s + s
    n = len(s)
    f = [-1] * (2 * n)
    k = 0
    for j in range(1, 2 * n):
        sj = s2[j]
        i = f[j - k - 1]
        while i != -1 and sj != s2[k + i + 1]:
            if sj < s2[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != s2[k + i + 1]:
            if sj < s2[k]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

def main():
    N, Q = map(int, input().split())
    S = input().strip()
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            l, r = int(query[1]) - 1, int(query[2])
            sub = S[l:r]
            words = lyndon_factorization(sub)
            if not words:
                print(0, 0)
                continue
            max_w = max(words)
            cnt = words.count(max_w)
            print(len(max_w), cnt)
        else:
            l, r = int(query[1]) - 1, int(query[2])
            sub = S[l:r]
            print(min_rotation(sub))

main()

Step-by-Step 解説

Step 1: Lyndon 語の定義

Lyndon 語とは、自身のすべての真の回転よりも辞書順で小さい文字列。例: "abc" は "bca", "cab" より小さい → Lyndon 語。

Step 2: Duval アルゴリズムの仕組み

3つのポインタ i（未処理先頭）, j（現在 Lyndon 語候補の先頭比較位置）, k（拡張位置）を使う。

• s[j] < s[k]: 候補をリセット（j = i）
• s[j] == s[k]: j++, k++
• s[j] > s[k]: 長さ k-j の Lyndon 語を i から出力

Step 3: Booth's Algorithm の仕組み

KMP の failure function を応用。s+s に対して処理し、最小回転の開始位置を O(N) で求める。

Step 4: クエリ処理

各クエリで部分文字列を切り出し、対応関数を呼び出す。全体計算量は $O(N + Q \cdot L)$（$L$ = クエリ長）。

よくあるミス

次のステップ

発展問題: 全文字列の Lyndon 分解の結果をオンラインで更新しながら、各 Lyndon 語の出現回数を管理せよ（動的 Lyndon 分解）。

自己評価