Đếm xuất hiện không chồng lấp

Hướng tiếp cận

Dùng KMP để xác định mọi vị trí có thể có xuất hiện của $P$ trong $S$, rồi áp dụng chiến lược tham lam để đếm số xuất hiện không chồng lấp.

Nhận xét quan trọng

Bài toán "chọn nhiều xuất hiện không chồng lấp nhất" tương đương bài kinh điển "chọn nhiều khoảng không giao nhau nhất trên trục số" khi mọi khoảng có cùng độ dài $|P|$. Khi mọi khoảng có chung độ dài, tham lam quét trái-phải, gặp khoảng nào còn dùng được thì lấy ngay cho ra kết quả tối ưu.

Trên KMP, khi gặp match đầy đủ ($j=|P|$), thay vì cập nhật $j\leftarrow \pi [|P|-1]$ (để bắt cả các match chồng lấp), ta đặt lại $j\leftarrow 0$ rồi tiếp tục quét — đây chính là phép "bỏ qua $|P|$ ký tự" của xuất hiện vừa lấy.

Thuật toán

1. Đọc $S,P$. Đặt $n=|S|$, $m=|P|$. Nếu $m>n$ in ra $0$ và dừng.
2. Tính mảng failure function $\pi [0..m-1]$ của $P$ theo KMP chuẩn.
3. Quét $S$ với biến $j$ là chỉ số đang khớp trên $P$, ban đầu $j=0$, đếm $\mathrm{c}\mathrm{n}\mathrm{t}=0$.
4. Với mỗi $i$ từ $0$ tới $n-1$:
   • Trong khi $j>0$ và $S[i]\ne P[j]$: $j\leftarrow \pi [j-1]$.
   • Nếu $S[i]=P[j]$: $j\leftarrow j+1$.
   • Nếu $j=m$: $\mathrm{c}\mathrm{n}\mathrm{t}\leftarrow \mathrm{c}\mathrm{n}\mathrm{t}+1$, $j\leftarrow 0$ (reset, không cho chồng lấp).
5. In $\mathrm{c}\mathrm{n}\mathrm{t}$.

Độ phức tạp

• Thời gian: $O(|S|+|P|)$.
• Bộ nhớ: $O(|P|)$ cho mảng failure function.