Tìm chu kỳ nhỏ nhất của xâu

Buổi 73-74 — Virtual CF Strings
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một xâu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh viết thường. Một số nguyên dương $P$ ($1 \le P \le N$) được gọi là một chu kỳ của $S$ nếu $S_i = S_{i - P}$ với mọi $P \le i < N$ (đánh số từ $0$), tức là $S$ là tiền tố của xâu thu được bằng cách lặp lại vô hạn lần tiền tố độ dài $P$ của $S$.

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

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