問題
英小文字の文字列 $S$（長さ $N$）が与えられる。$S$ の 最小周期 $p$ を求めよ。$p$ が周期とは $1 \le p \le N$ かつ全ての $i$（$1 \le i \le N-p$）で $S_i = S_{i+p}$ が成り立つこと。最小の $p$ を出力せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N = |S|$ | $1 \le N \le 5\times10^5$ | 文字列長 |
| 文字種 | 英小文字 a-z | — |
| 出力 | $1 \le p \le N$ | 最小周期 |
入出力例
入力例1 / 出力例1
ababab
→ 2入力例2 / 出力例2
abcabcab
→ 3ababab は ab の繰り返しで周期2。abcabcab は $S_i=S_{i+3}$ を満たし周期3（$N$ が3の倍数でなくてもよい）。
概念図
ヒント
ヒント1（方向性）
「周期 $p$」と「境界(border)」は表裏一体。長さ $b$ の border があると $p = N - b$ が周期。最大 border ↔ 最小周期。
ヒント2（アプローチ）
Z配列 $Z[i]$ =「$S$ と位置 $i$ から始まる接尾辞の最長共通接頭辞長」を $O(N)$ で計算。$p$ が周期 $\iff Z[p] = N - p$。
ヒント3（ほぼ答え）
for p in range(1, n):
if z[p] == n - p:
return p
return n模範解答
import sys
def z_algorithm(s):
n = len(s)
z = [0] * n
z[0] = n
l = r = 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]
return z
def main():
s = sys.stdin.buffer.readline().strip().decode()
n = len(s)
z = z_algorithm(s)
period = n
for p in range(1, n):
if z[p] == n - p:
period = p
break
print(period)
main()計算量 $O(N)$。各位置は $[l,r)$ を超えた分だけ比較が進むため償却 $O(N)$。
Step-by-Step 解説
Step 1: Z配列の定義
$Z[i]$ は $S$ と $S[i:]$ の最長共通接頭辞長。$Z[0]$ は慣例で $N$。
Step 2: [l, r) ウィンドウで再利用
既知の一致区間 $[l, r)$ の内側 ($i < r$) では $Z[i-l]$ を使い初期値を min(r-i, z[i-l]) に設定でき、無駄な比較を省ける。
Step 3: 素朴拡張とウィンドウ更新
初期値から先を1文字ずつ照合。$i + Z[i]$ が $r$ を超えたらウィンドウを更新。
Step 4: 周期判定
$p$ から先が接頭辞と一致（$Z[p] = N - p$）なら $p$ は周期。最小の $p$ を返す。$N$ は常に周期なので既定値。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| $Z[0]$ を 0 にする | 定義の取り違え | $Z[0] = N$ に固定 |
| 周期条件を $Z[p] \ge N-p$ | 一致長は最大 $N-p$ | ちょうど z[p] == n - p |
| border と period の混同 | $p = N - b$ の変換ミス | period を直接 $Z[p]=N-p$ で判定 |
| 末尾改行を含める | readline の \n | .strip() で除去 |
次のステップ
- 発展: $N \bmod p = 0$ なら「$p$ 文字の完全な繰り返し」と判定
- 発展: KMP failure 関数でも同じ最小周期が求まる（比較）
- 次回予告: Mo's Algorithm（区間相異なる値の個数）
自己評価
理解度: / /
自分の回答:
気づき・メモ: