Đếm xuất hiện mẫu (KMP)

Hướng tiếp cận

Đây là bài toán đếm số lần xuất hiện của một xâu mẫu $P$ trong xâu văn bản $S$, cho phép chồng lấp. Cách làm ngây thơ — duyệt mọi vị trí bắt đầu $i\in [0,N-M]$ rồi so sánh từng ký tự — có độ phức tạp $O(N·M)$. Với $N,M$ lên tới ${10}^6$, cách này không đủ nhanh.

Thuật toán KMP (Knuth–Morris–Pratt) giải bài toán này trong $O(N+M)$ nhờ tận dụng cấu trúc của chính xâu mẫu để tránh so sánh lại các ký tự đã so sánh.

Nhận xét quan trọng

1. Hàm prefix (failure function): với mỗi $i$, $\pi [i]$ là độ dài lớn nhất của một tiền tố thực sự (proper prefix) của $P[0..i]$ mà đồng thời cũng là hậu tố của $P[0..i]$. Hàm này có thể tính trong $O(M)$.
2. Quét văn bản: ta duy trì biến $j$ = số ký tự khớp hiện tại. Khi gặp ký tự không khớp tại $S[i]$ với $P[j]$, ta nhảy về $j=\pi [j-1]$ thay vì lùi lại — đây chính là chỗ tiết kiệm thời gian.
3. Đếm chồng lấp: khi $j$ đạt $M$ (đã khớp hết mẫu), ta tăng đếm rồi đặt $j=\pi [M-1]$. Điều này cho phép tiếp tục tìm các lần xuất hiện tiếp theo có thể chồng lấp với lần vừa tìm.

Thuật toán

# Tính pi[0..M-1]
pi[0] = 0
k = 0
for i = 1..M-1:
    while k > 0 and P[k] != P[i]:
        k = pi[k-1]
    if P[k] == P[i]:
        k += 1
    pi[i] = k

# Quét S
count = 0
j = 0
for i = 0..N-1:
    while j > 0 and P[j] != S[i]:
        j = pi[j-1]
    if P[j] == S[i]:
        j += 1
    if j == M:
        count += 1
        j = pi[M-1]

Cả hai vòng while đều chỉ có thể giảm $j$ (hoặc $k$) tổng cộng đúng bằng số lần biến đó được tăng. Do đó tổng số thao tác trong toàn bộ thuật toán là $O(N+M)$.

Độ phức tạp

• Thời gian: $O(N+M)$.
• Bộ nhớ: $O(M)$ cho mảng $\pi$.