問題
文字列 $S$（長さ $N$）について次を求める。
- $S$ の proper border 全てを長さ昇順で出力。
- 各 $i$ ($1 \le i \le N$) で $S[0..i-1]$ の最小周期 $p_i$ を出力。
- 各 $i$ で $S[0..i-1] = T^k$ となる最大の $k$ を出力。
制約
$1 \le N \le 2 \times 10^5$
$S$ は英小文字
時間制限: 2sec
メモリ: 256MB
入出力例
入力例 1
8
abababab出力例 1
6 4 2
1 1 2 2 2 2 2 2
1 1 1 2 1 3 1 4概念図: KMP failure 配列 と border
$\pi[i]$ = $S[0..i]$ の最長 proper border の長さ。チェーンを辿ると全ての proper border の長さが得られる。
ヒント (段階的開示)
ヒント1: 方向性
$\pi[i]$ から「proper border 全体」「最小周期」「繰り返し回数」を全て派生できる。
ヒント2: アプローチ
(a) proper border:
(b) 最小周期:
(c) 繰り返し:
cur = π[N-1]; while cur > 0: push cur; cur = π[cur-1](b) 最小周期:
cand = i - π[i-1]; i % cand == 0 ? cand : i(c) 繰り返し:
i % p_i == 0 ? i / p_i : 1
ヒント3: KMP 構築
pi = [0]*N
for i in range(1, N):
j = pi[i-1]
while j > 0 and S[i] != S[j]:
j = pi[j-1]
if S[i] == S[j]: j += 1
pi[i] = j模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N = int(input())
S = input().strip()
pi = [0] * N
for i in range(1, N):
j = pi[i-1]
while j > 0 and S[i] != S[j]:
j = pi[j-1]
if S[i] == S[j]:
j += 1
pi[i] = j
borders = []
cur = pi[N-1] if N >= 1 else 0
while cur > 0:
borders.append(cur)
cur = pi[cur-1]
borders.sort()
print(*borders)
period_out = []; rep_out = []
for i in range(1, N + 1):
cand = i - pi[i-1]
p = cand if i % cand == 0 else i
period_out.append(p)
rep_out.append(i // p if i % p == 0 else 1)
print(*period_out)
print(*rep_out)
solve()
Step-by-Step 解説
1KMP failure 配列
$\pi[i] = $ $S[0..i]$ の最長 proper border の長さ。$O(N)$ で構築。
$\pi[i] = $ $S[0..i]$ の最長 proper border の長さ。$O(N)$ で構築。
2全 proper border
$\pi$ チェーンを最後から辿る。長さの降順列が得られるので
$\pi$ チェーンを最後から辿る。長さの降順列が得られるので
sort で昇順に。
3最小周期
$b = \pi[i-1]$、$\text{cand} = i - b$。$i \bmod \text{cand} = 0$ なら真の周期、それ以外は $i$ 自身。
$b = \pi[i-1]$、$\text{cand} = i - b$。$i \bmod \text{cand} = 0$ なら真の周期、それ以外は $i$ 自身。
4繰り返し回数
$S[0..i-1] = T^k$ ⇔ $|T| \mid i$ かつ周期 $|T|$。$k = i / p_i$。
$S[0..i-1] = T^k$ ⇔ $|T| \mid i$ かつ周期 $|T|$。$k = i / p_i$。
計算量
KMP: $O(N)$
Border 列挙: $O(\text{number of borders}) = O(N)$
周期・繰り返し: $O(N)$
合計: $O(N)$
Border 列挙: $O(\text{number of borders}) = O(N)$
周期・繰り返し: $O(N)$
合計: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
while 内で π[j] を使う | 定義のずれ | j = π[j-1] を使う |
| 周期判定で常に $i - b$ を採用 | 非倍数時の処理漏れ | if i % cand == 0 ガード |
| 空文字列 $N=0$ | $\pi[-1]$ 参照でクラッシュ | if N >= 1 ガード |
| borders 降順のまま出力 | 問題が昇順を要求 | .sort() |
| 出力が大きく遅い | 1 要素ずつ print | print(*list) または ' '.join |
次のステップ
- 発展: Z 配列との統合（prefix-substring 一致と border の同時取得）
- 応用: 最短 supersuffix で全体を周期化する付加
- 関連: Eertree（回文 border 管理）、Suffix Automaton