Day 052-Q1 — Lyndon分解 + Duval Algorithm（最小回転・辞書順最小周期分解）

2026-06-05 赤色 Master / Phase 8+ ★★★★★★★★★ Lyndon分解 / Duval Algorithm / Booth's Algorithm

問題

長さ $N$ の文字列 $S$（小文字英字のみ）に対して以下の2種類のクエリを $Q$ 回処理せよ。

  • クエリ type 1: 1 l r — $S[l..r)$（0-indexed 半開区間）の Lyndon 分解を求め、各 Lyndon 語の長さを空白区切りで出力せよ。
  • クエリ type 2: 2 l r — $S[l..r)$ の辞書順最小回転（Booth's Algorithm）の開始位置（相対 0-indexed）を出力せよ。

制約

パラメータ範囲
$N$$1 \le N \le 2 \times 10^5$
$Q$$1 \le Q \le 10^4$
$l, r$$0 \le l < r \le N$
文字種小文字英字のみ
時間制限2秒

入出力例

入力例 1

11 3
abababacaba
1 0 8
2 0 8
1 3 11

出力例 1

2 2 2 2
0
4 4

"ababab ac" (S[0..8]) の Lyndon 分解: "ab"×4 = [2,2,2,2]。最小回転開始位置 = 0（"ababacab" が最小回転）。

概念図: Duval Algorithm の動作

Duval Algorithm: s = "aababc" の Lyndon 分解 s: a a b a b c 0 1 2 3 4 5 Step 1: i=0, j=0, k=1: s[0]='a' == s[1]='a' → j++, k++ → j=1,k=2 Step 2: s[1]='a' < s[2]='b' → j=i=0, k=3 （より長いLyndon語候補） Step 3: s[0]='a' == s[3]='a' → j++, k++ → j=1,k=4 Step 4: s[1]='a' < s[4]='b' → j=0, k=5 Step 5: s[0]='a' < s[5]='c' → j=0, k=6 (k=n) Step 6: k=6=n: i=0≤j=0 → 長さ k-j=6-0=6 の Lyndon 語 → i=6 結果: "aababc" → Lyndon 語: ["aababc"] (長さ6) Lyndon 語: 自身のすべての真の接尾辞より辞書順で小さい文字列

ヒント（段階的開示）

ヒント1: 方向性
Lyndon 語とは「それ自身の全ての真の回転の中で辞書順最小」な文字列（= 全ての真の接尾辞より小さい）。 Duval Algorithm は 3 ポインタ i, j, k で $O(N)$ の Lyndon 分解を実現する。
ヒント2: アプローチ
  • Duval Algorithm: i = 未処理先頭、j = 周期リセット位置、k = 比較位置
  • s[j] == s[k]: 両方進める（周期の延長候補）
  • s[j] < s[k]: j = i にリセット（より長い Lyndon 語が作れる）
  • s[j] > s[k]: (k-j) の周期で Lyndon 語を切り出す
  • Booth's Algorithm: S+S 上で KMP failure 関数的処理。最小回転位置を追跡
ヒント3: コード骨格 
def lyndon_decomposition(s):
    result = []
    n = len(s); i = 0
    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(k - j)
            i += k - j
    return result

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

模範解答 (Python)

import sys
input = sys.stdin.readline

def lyndon_decomposition(s):
    """Duval Algorithm: O(N) で Lyndon 分解"""
    result = []
    n = len(s); i = 0
    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(k - j)
            i += k - j
    return result

def booth(s):
    """Booth's Algorithm: O(N) で最小回転位置を返す"""
    ss = s + s
    n = len(ss)
    f = [-1] * n
    k = 0
    for j in range(1, n):
        sj = ss[j]
        i = f[j - 1 - k]
        while i != -1 and sj != ss[k + i + 1]:
            if sj < ss[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != ss[k + i + 1]:
            if sj < ss[k]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

def solve():
    N, Q = map(int, input().split())
    S = input().strip()
    out = []
    for _ in range(Q):
        line = input().split()
        t, l, r = int(line[0]), int(line[1]), int(line[2])
        sub = S[l:r]
        if t == 1:
            lengths = lyndon_decomposition(sub)
            out.append(' '.join(map(str, lengths)))
        else:
            pos = booth(sub)
            out.append(str(pos))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1Lyndon 語の定義
文字列 $w$ が Lyndon 語 ⟺ $w$ の全ての真の接尾辞 $s$ に対して $w < s$（辞書順）。 等価条件: $w$ が自身の全ての真の回転の中で辞書順最小。
2Duval Algorithm の核心
ポインタ i（未処理先頭）、j（周期候補の先頭）、k（比較位置）。 $s[j] < s[k]$ のとき $j = i$ にリセット = 「長い Lyndon 語が作れる可能性」を探る。 $s[j] > s[k]$ のとき、$s[i..k-1]$ は $(k-j)$ を周期に持ち、$s[i..i+(k-j)-1]$ が Lyndon 語。
3Booth's Algorithm
$S+S$ 上で KMP の failure 関数を計算しながら、最小回転の開始位置 $k$ を追跡。 $ss[j] < ss[k+i+1]$ のとき $k = j - i - 1$（より小さい候補に更新）。
4Lyndon 分解の一意性
任意の文字列は Lyndon 語の辞書順非増加積 $w_1 \ge w_2 \ge \ldots \ge w_k$ として一意に分解される（Chen-Fox-Lyndon 定理）。

計算量

Duval Algorithm: $O(N)$ 時間・$O(1)$ 追加空間
Booth's Algorithm: $O(N)$ 時間・$O(N)$ 追加空間
クエリ処理: $O(Q \cdot (r-l))$ 全体
最悪: $O(Q \cdot N)$ — 大きな $Q, N$ では事前分解が必要

よくあるミス

ミス原因正しい書き方
j = i のリセット忘れs[j] < s[k] 時に j を i に戻さないif s[j] < s[k]: j = i
切り出しループの条件i <= j でなく i < k にしてしまうwhile i <= j: i += k - j
Booth の f[j-k] 境界j - k が負になりうるk を更新してから f[j-k] を参照
半開区間の切り出しS[l:r+1] としてしまうS[l:r]（Python は半開）

次のステップ

  • 発展問題: Lyndon-Schützenberger 定理（$u^a = v^b$ ならば共通の Lyndon 根を持つ）の実装検証
  • 関連: Suffix Array の隣接要素と Lyndon 分解の関係（SA の連続区間 = Lyndon 語の対応）
  • 応用: 辞書順最小回転文字列をキーとした文字列の正規化・比較

自己評価