Phân Tách Xâu Tối Ưu

Buổi 56 — Suffix Array & LCP
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề 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.
Draft saved