Chu Kỳ Của Chuỗi

Buổi 53 — String Hashing
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho một chuỗi $S$ gồm $N$ ký tự in thường. Tìm chu kỳ nhỏ nhất $p$ của chuỗi, tức là số nguyên dương $p$ nhỏ nhất sao cho $S[i] = S[i + p]$ với mọi $1 \le i \le N - p$.

Nói cách khác, $p$ là độ dài nhỏ nhất sao cho chuỗi $S$ có thể được tạo ra bằng cách lặp lại một tiền tố có độ dài $p$ (cắt bớt nếu cần).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa chuỗi $S$ có độ dài $N$.
Dữ liệu ra
  • In ra một số nguyên $p$ — chu kỳ nhỏ nhất.
Ví dụ
Input Output
6\nabcabc 3
4\naaaa 1
5\nabcde 5
Giới hạn
  • $1 \le N \le 10^6$
  • Chuỗi chỉ chứa ký tự in thường từ a đến z.
Draft saved