Day 129-Q3 | Booth's Algorithm（巡回文字列の辞書順最小回転）

問題

長さ$N$の文字列$S$が与えられる。$S$を巡回的にシフトして得られる$N$個の文字列（$k$文字左シフト、$k=0,\dots,N-1$）のうち辞書順最小のものを求めよ。

入力形式

制約

$1 \le |S| \le 200000$

$S$は英小文字のみ

入出力例

入力例1

baaa

出力例1

1
aaab

k=0:baaa, k=1:aaab, k=2:aaba, k=3:abaa。最小は aaab（シフト量1）。

概念図

ヒント（段階的開示）

ヒント1（方向性）

愚直に$N$通り生成して比較すると$O(N^2)$。$S+S$の中に長さ$N$の全回転が部分文字列として現れることに注目し、KMPの失敗関数に似た仕組みで全回転を同時に比較しながら候補を絞り込む。

ヒント2（アプローチ）

「現在の最良候補の開始位置k」と「比較中の候補位置」を同時に1文字ずつ進め、不一致時にどちらが優れるか判定して勝った方を新候補にする二重ポインタ法（Booth's Algorithm）。戻り先テーブルで既知の情報を再利用し全体をO(N)に抑える。

ヒント3（誘導）

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

返り値kが最小回転の開始位置（0-indexed）。

模範解答 (Python)

import sys


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


def solve():
    s = sys.stdin.readline().strip()
    k = least_rotation(s)
    rotated = s[k:] + s[:k]
    print(k)
    print(rotated)


solve()

Step-by-Step 解説

1なぜS+Sを使うのか
長さNの巡回シフトはすべてS+Sの中の長さN連続部分文字列として現れる（開始位置0..N-1）。

2二重ポインタでの同時比較
現在の最良候補kと新候補を同時に伸ばしながら比較。KMP同様、不一致位置の情報(f配列)を使い次の比較開始位置をO(1)償却で決める。

3勝敗判定と更新
比較文字sjが現候補の対応文字より小さければ新候補が優れているのでkを更新。大きければ据え置き、fテーブルだけ更新。

4失敗関数の役割
f[x]はKMPの失敗関数と同型の「次に比較を再開すべき候補内位置」を表す。

5計算量
全体でO(N)。S+Sの長さは2Nだが定数倍のみで漸近計算量は変わらない。

よくあるミス

ミス	原因	正しい書き方
S+Sを使わずインデックス計算だけで巡回を扱う	境界処理が破綻する	素直にs+sを作り通常の文字列アルゴリズムとして扱う
失敗関数の添字をKMPと同じだと思い込む	2候補を同時に進める構造の違いを見落とす	`f[j-k-1]`のように候補開始位置kからの相対位置で添字を取る
出力文字列のスライスでオフバイワン	ss[k:k+n]の計算ミス	元のsから`s[k:] + s[:k]`で構成する
周期文字列(全シフトが同値)を想定していない	例: "aaaa"	タイでも有効な最小開始位置を返すことを確認する

次のステップ

発展: 巡回同型判定は両方の最小回転を求めて文字列比較するだけでO(N)
次回予告: 一般化中国剰余定理（Generalized CRT）

自己評価

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

Day 129-Q3 — Booth's Algorithm（巡回文字列の辞書順最小回転）

問題