Mô phỏng thuật toán Tìm chuỗi con (ngây thơ)

Naive String Matching · Nhóm: Chuỗi

Tìm chuỗi con bằng so khớp ngây thơ: trượt cửa sổ dài bằng mẫu qua text, tại mỗi vị trí so từng ký tự của mẫu, khớp hết thì báo tìm thấy.

Ý tưởng

Với mỗi vị trí dịch i trong text, đặt cửa sổ text[i..i+m).

So lần lượt pattern[j] với text[i+j]; lệch thì bỏ dở, trượt sang i kế tiếp.

Nếu so hết m ký tự đều trùng thì mẫu xuất hiện tại vị trí i.

Vì sao đúng

Đơn giản nhất, không cần tiền xử lý, dễ hiểu và đúng; là điểm khởi đầu trước khi học các thuật toán nhanh hơn như KMP.

Mã Python

def strstr(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i          # found
    return -1                 # not found

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.