Thuật toán tìm chuỗi KMP là gì: cách hoạt động, code và độ phức tạp

KMP giải bài toán gì

Bài toán tìm chuỗi hỏi một mẫu ngắn xuất hiện ở đâu trong một văn bản dài hơn. Cách ngây thơ thử mọi vị trí bắt đầu và so sánh từng ký tự. Trên văn bản thông thường nó nhanh, nhưng trên dữ liệu lặp lại nhiều thì chậm: tìm aaaab trong aaaaaaaaaa phải so sánh gần hết mẫu ở mỗi vị trí, cho thời gian O(n × m).

KMP không bao giờ đọc lại một ký tự của văn bản sau khi không khớp. Donald Knuth, James H. Morris và Vaughan Pratt công bố nó năm 1977 trong bài “Fast Pattern Matching in Strings”.

Ý tưởng bằng lời đơn giản

Giả sử bạn tìm mẫu ABABC, đã khớp ABAB, và ký tự văn bản tiếp theo không phải C. Phần vừa khớp, ABAB, kết thúc bằng AB, cũng chính là phần đầu của mẫu. Vì vậy bạn đã biết lần thử tiếp theo bắt đầu với 2 ký tự đã khớp, và có thể tiếp tục so sánh từ vị trí 2 của mẫu thay vì bắt đầu lại.

Hàm tiền tố lưu các con số này. pi[i] là độ dài của tiền tố thực sự dài nhất của pattern[0..i] đồng thời là hậu tố của nó (thực sự nghĩa là không phải cả chuỗi).

Ví dụ, pi[4] = 3 vì ABABA bắt đầu và kết thúc bằng ABA. pi[5] = 0 vì không tiền tố nào của ABABAC kết thúc bằng C.

Ví dụ từng bước

Tìm mẫu ABABC (hàm tiền tố 0, 0, 1, 2, 0) trong văn bản ABABABC. Biến k đếm số ký tự của mẫu đang khớp.

Con trỏ văn bản tiến lên 7 lần và không bao giờ lùi. Cách ngây thơ sẽ bắt đầu lại ở vị trí 1 và so sánh lại một số ký tự.

Cài đặt bằng Python

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

Độ phức tạp thời gian và không gian

Thuật toán ngây thơ là O(n × m) trong trường hợp xấu nhất nhưng thường gần O(n) trên văn bản ngôn ngữ tự nhiên, nên lợi thế của KMP thể hiện chủ yếu trên dữ liệu lặp lại.

Biến thể và lỗi thường gặp

• Lệch một đơn vị khi lùi: sau khi không khớp, đặt k = pi[k - 1], không phải pi[k]. pi được đánh chỉ số theo vị trí khớp cuối cùng.
• Dùng if thay vì while cho bước lùi: bạn có thể cần lùi nhiều lần liên tiếp trước khi một ký tự khớp.
• Quên đặt lại k sau khi khớp hoàn toàn: đặt k = pi[k - 1] để tìm các vị trí khớp chồng nhau, hoặc k = 0 cho các vị trí không chồng.
• Mẹo nối chuỗi: tính hàm tiền tố của pattern + separator + text, dùng một ký tự phân cách không xuất hiện ở cả hai; mọi vị trí có giá trị bằng m là điểm kết thúc của một lần khớp.
• Thuật toán Z tính một mảng có liên quan chặt chẽ và cũng tìm kiếm trong O(n + m).

Khi nào dùng và ứng dụng thực tế

• Bài phỏng vấn: cài đặt strStr(), shortest palindrome (hàm tiền tố của s + "#" + reversed(s)), repeated substring pattern, chu kỳ nhỏ nhất của một chuỗi (m - pi[m - 1]).
• Thực tế: tìm kiếm trong chuỗi DNA và luồng gói tin mạng, nơi thời gian tuyến tính trong trường hợp xấu nhất quan trọng.