Chu Kỳ Ngắn Nhất

Buổi 54 — KMP & Z-function
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Một số nguyên dương $p$ ($1 \le p \le |S|$) được gọi là chu kỳ của xâu $S$ nếu với mọi $0 \le i < |S| - p$, ta có $S[i] = S[i + p]$ (nói cách khác, $S$ là tiền tố của xâu tạo bởi việc lặp lại vô hạn $S[0..p-1]$).

Hãy tìm chu kỳ $p$ nhỏ nhất của xâu $S$.

Dữ liệu vào
  • Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là chu kỳ nhỏ nhất của $S$.
Ví dụ
Input Output
abcabca 3
aaaa 1
Giới hạn
  • $1 \le |S| \le 10^6$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved