Phân Tách Xâu Tối Ưu
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Đề bài
Cho xâu $S$ gồm các chữ cái in thường. Hãy phân tách $S$ thành số phần ít nhất sao cho mỗi phần là một xâu con đã xuất hiện trước đó trong $S$ (tính từ đầu), hoặc là một ký tự đơn lẻ (nếu chưa từng xuất hiện).
Cụ thể: duyệt từ trái sang phải, tại mỗi vị trí $i$, tìm xâu con dài nhất $S[i..j]$ sao cho $S[i..j]$ đã xuất hiện ở đâu đó trong $S[0..i-1]$. Nếu tìm được, cắt phần $S[i..j]$ thành một phần. Nếu không tìm được, cắt $S[i]$ thành một phần riêng.
Đây là bài toán nén LZ (Lempel-Ziv factorization) sử dụng mảng hậu tố.
In ra số phần sau khi phân tách.
Dữ liệu vào
Một dòng chứa xâu $S$ ($1 \le |S| \le 2 \times 10^5$) chỉ gồm các chữ cái in thường.
Dữ liệu ra
Một số nguyên duy nhất là số phần ít nhất.
Ví dụ
| Input | Output |
|---|---|
| abcabcabc | 4 |
Giới hạn
- $1 \le |S| \le 2 \times 10^5$
- $S$ chỉ gồm chữ cái in thường.
Community Discussion