Xâu Phủ Ngắn Nhất

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

Xâu $C$ được gọi là xâu phủ (cover) của xâu $S$ nếu mọi vị trí trong $S$ đều thuộc về ít nhất một lần xuất hiện của $C$ trong $S$ (các lần xuất hiện của $C$ có thể giao nhau).

Hãy tìm độ dài ngắn nhất của một xâu phủ của $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à độ dài xâu phủ ngắn nhất của $S$.
Ví dụ
Input Output
ababa 3
abaababa 3
Giới hạn
  • $1 \le |S| \le 10^6$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved