Tìm chu kỳ nhỏ nhất của xâu
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion