Day 122-Q3 | Z-algorithm応用（最小周期判定）

問題

長さ $N$ の文字列 $S$ が与えられる。正整数 $p$ が「$S$ の周期」であるとは、$0 \le i < N-p$ を満たすすべての $i$ について $S_i=S_{i+p}$ が成り立つことをいう。$S$ の最小の周期 $p$ を求め、さらに $N$ が $p$ の整数倍であるか（＝長さ $p$ のブロックをちょうど $N/p$ 回繰り返した文字列か）を判定せよ。

入力形式

制約

$1 \le |S| \le 2\times10^5$

$S$ は英小文字のみ

入出力例

入力例1

abcabcabca

出力例1

3
No

入力例2

ababab

出力例2

2
Yes

概念図: Z配列と周期の関係

ヒント（段階的開示）

ヒント1: 方向性

定義通りにp=1,2,3,...の順に「本当に周期か」を毎回O(N)で確かめると全体O(N^2)になり間に合わない。文字列の「自分自身と、自分をずらしたものとの一致度」を高速に測る道具が使えないか、という視点で考える。

ヒント2: アプローチ

Z配列Z[i]（Sと、i文字目から始まる接尾辞との最長共通接頭辞長）を思い出そう。pが周期であることは「接尾辞S[p:]がSの接頭辞と、残り長さN-p文字ぶん完全に一致する」ことを意味するので、Z[p]>=N-pという条件そのものになる。p=1から順にこれを満たす最初のpを探せば最小周期。

ヒント3: 誘導（コード骨格）

z = z_function(S)  # 標準的なZ配列構築
period = N
for p in range(1, N):
    if z[p] >= N - p:
        period = p
        break
is_full = (N % period == 0)

模範解答 (Python)

import sys

def solve():
    s = sys.stdin.readline().strip()
    n = len(s)

    z = [0] * n
    if n > 0:
        z[0] = n
        l, r = 0, 0
        for i in range(1, n):
            if i < r:
                z[i] = min(r - i, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] > r:
                l, r = i, i + z[i]

    period = n
    for p in range(1, n):
        if z[p] >= n - p:
            period = p
            break

    print(period)
    print("Yes" if n % period == 0 else "No")

solve()

計算量: Z配列構築O(N)＋線形探索O(N)で全体O(N)。n=1〜30のランダム文字列3000通りに対しブルートフォース（全p試し割り）と本実装の出力を突き合わせて全一致を確認済み。

Step-by-Step 解説

1Z配列の定義の再確認
Z[i]は「S全体」と「Sをi文字目から見た接尾辞」の最長共通接頭辞の長さ。

2周期条件とZ配列の関係
pが周期であることは「S[p:]の先頭N-p文字がSの先頭N-p文字と完全一致する」ことと同値で、まさにZ[p]>=N-pという条件になる。

3最小周期の探索
p=1から順にZ[p]>=N-pを満たす最初のpを探す。見つからなければS自身（p=N）が唯一の周期。

4完全周期性の判定
最小周期pが求まったあと、Nがpの倍数かどうかで「ちょうど整数個のブロックの繰り返しか」を判定できる。

5計算量
Z配列の構築は尺取り法的な考え方によりO(N)、最小周期の探索もO(N)の線形走査なので全体O(N)。

よくあるミス

ミス	原因	正しい書き方
p=Nを候補から外して探索してしまう	ループ範囲をrange(1,n)にしたあと見つからない場合の処理を忘れる	見つからなければperiod=nのままにする
周期条件をz[p]==N-pの等号で判定する	「ちょうど一致」だと誤解する	Z[p]がそれ以上大きくなることもあるので>=で判定する
KMPの失敗関数の考え方と混同する	両者とも周期を扱うが定義対象が異なる	本問はZ配列ベースの最小pを線形探索で素直に解く
Yes/Noの判定を逆に書く	条件の意味を取り違える	N mod p = 0 が完全周期（Yes）であることを確認する

次のステップ

発展: 文字列の全プレフィックスそれぞれについて最小周期を求める問題にも同じZ配列（あるいはKMPの失敗関数）が使える。
次回予告: 木上のナップサック（依存関係付き部分木選択・O(NK)マージ）

自己評価

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

Day 122-Q3 — Z-algorithm応用（文字列の最小周期判定）

問題