Day 148-Q2 | Main-Lorentz法（簡略版）

問題

長さ$N$の文字列$S$（0-indexed）が与えられる。三つ組$(i,j,p)$が「周期$p$の極大周期区間」であるとは次をすべて満たすことをいう。

$0\le i<j\le N-1$、区間長$L=j-i+1$は$L\ge 2p$
$S[i..j]$内のすべての$k$（$i\le k\le j-p$）で$S[k]=S[k+p]$
左方向に極大: $i=0$または$S[i-1]\ne S[i-1+p]$
右方向に極大: $j=N-1$または$S[j+1]\ne S[j+1-p]$

$p$は最小周期である必要はなく、同じ区間が複数の$p$で重複カウントされうる。$p=1,\dots,\lfloor N/2\rfloor$すべてについて条件を満たす$(i,j)$の総数を求めよ。

入力形式

制約

$1 \le |S| \le 50$

$S$ は英小文字のみ

入出力例

入力例1

aabaaba

出力例1

入力例2

abcabcabc

出力例2

概念図：等号配列の"1の塊"が極大周期区間になる（S="aabaaba", p=3）

ヒント（段階的開示）

ヒント1（方向性）

固定した周期長$p$について$S[k]=S[k+p]$の0/1配列を作ると、連続する1の塊がそのまま「周期$p$の極大周期区間の候補」になる。

ヒント2（アプローチ）

長さ$r$の1の塊は区間長$r+p$の周期区間に対応。$r+p\ge2p\iff r\ge p$のときのみカウントする。塊は配列上ですでに左右へ拡張不能なので極大性は自動的に満たされる。

ヒント3（誘導）

def count_runs(s):
    n = len(s)
    total = 0
    for p in range(1, n // 2 + 1):
        m = n - p
        i = 0
        while i < m:
            if s[i] == s[i + p]:
                j = i
                while j < m and s[j] == s[j + p]:
                    j += 1
                r = j - i
                if r >= p:
                    total += 1
                i = j
            else:
                i += 1
    return total

模範解答 (Python)

import sys

def count_runs(s):
    n = len(s)
    total = 0
    for p in range(1, n // 2 + 1):
        m = n - p
        i = 0
        while i < m:
            if s[i] == s[i + p]:
                j = i
                while j < m and s[j] == s[j + p]:
                    j += 1
                r = j - i
                if r >= p:
                    total += 1
                i = j
            else:
                i += 1
    return total


def main():
    s = sys.stdin.readline().strip()
    print(count_runs(s))


main()

Step-by-Step 解説

1周期を持つことと等号配列の対応
$S[i..j]$が周期$p$を持つとは、等号配列$e_p[k]=[S[k]=S[k+p]]$の$e_p[i..j-p]$がすべて1であることと同値。

2極大性が塊の境界と一致
1の塊の前後が0または配列外であることが、そのまま極大性条件（$S[i-1]\ne S[i-1+p]$など）に対応する。

3$r\ge p$の意味
塊長$r$は区間長$L=r+p$から$p$を引いたもの。$L\ge2p\iff r\ge p$なので単純な整数比較で判定できる。

4計算量
各$p$につき配列全体を1度舐めるため$O(N-p)$かかり、全体は$O(N^2)$（本問の簡略版）。真のMain-Lorentz法は分割統治で$O(N\log N)$を達成する。

よくあるミス

ミス	原因	正しい書き方
条件を$r\ge2p$にしてしまう	区間長$L=r+p$と周期$p$の関係を勘違い	$L\ge2p\iff r\ge p$を正しく導出する
走査範囲を$k=0,\dots,n-1$にしてしまう	$S[k+p]$が範囲外になることを見落とす	範囲は$k=0,\dots,n-p-1$（`m=n-p`）に限定する
同じ区間・周期を複数回カウント	塊検出後に`i`を1ずつしか進めない	塊を検出したら`i=j`（塊の直後）にジャンプする
文献の"runs"（最小周期のみ）と混同	本問はあえて全ての$p$を数える簡略版	非最小周期も含む総数であり文献の値とは異なりうると理解する
出力例2で他の周期も検出されると誤解	$p=1,2$の等号配列を検証していない	手で$e_1,e_2$を書き出し塊長が$r\ge p$を満たさないことを確認する

次のステップ

発展: 分割統治＋Z関数で中央をまたぐ周期のみ$O(\log N)$個の候補に絞る真の$O(N\log N)$版を実装し$N=2\times10^5$で動作確認せよ。
次回予告: Dulmage-Mendelsohn分解（二部グラフの最大マッチング構造を3成分に分解する）

自己評価

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

Day 148-Q2 — Main-Lorentz法（簡略版・全周期に対する極大周期区間の数え上げ）

問題