Chuyển tới nội dung chính

Tìm chuỗi con (KMP, Rabin-Karp)

Bạn sẽ học được gì

Bài toán muôn thuở: tìm một mẫu (pattern) trong một văn bản (text) dài — như Ctrl+F trong trình duyệt. Cách ngây thơ tốn O(n·m). Bạn sẽ học hai thuật toán nhanh O(n + m): KMP dùng mảng prefix-function để không bao giờ "lùi" trong văn bản, và Rabin-Karp dùng rolling hash để so sánh cả đoạn chỉ bằng một con số. Đây là bài 🔴 khó — ta sẽ đi thật chậm và sâu.

1. Trực quan: dò mẫu trên một dải băng​

Hình dung văn bản là một dải băng dài và mẫu là một thanh trượt ngắn bạn rê dọc theo nó. Tại mỗi vị trí, bạn so từng ký tự. Khớp hết → tìm thấy. Lệch một chỗ → trượt thanh sang phải rồi thử lại.

   text:    A B A B A B C A B A B A B C
   pattern:     A B A B C
                     ^ lech o day -> truot tiep

Cách ngây thơ (naive): với mỗi vị trí bắt đầu (có n vị trí), so tối đa m ký tự → O(n·m). Với văn bản triệu ký tự và mẫu nghìn ký tự, đó là cả tỉ phép so. Ta cần khôn hơn.

2. Cách ngây thơ và điểm yếu của nó​

Đang tải trình chạy code…

Điểm yếu: khi gặp lệch, naive vứt bỏ mọi thông tin đã so và bắt đầu lại từ đầu mẫu, đồng thời lùi con trỏ văn bản. Với chuỗi nhiều lặp lại (AAAA...), nó tệ nhất O(n·m). KMP sửa đúng chỗ lãng phí này.

3. KMP: mảng prefix-function (failure function)​

Ý tưởng cốt lõi của KMP (Knuth–Morris–Pratt): khi đang khớp được một đoạn của mẫu rồi gặp lệch, ta đã biết đoạn vừa khớp đó trông như thế nào. Nếu đoạn đó có một tiền tố cũng là hậu tố (prefix = suffix), ta có thể trượt mẫu để tiền tố đó vào đúng vị trí — không cần lùi văn bản.

Bảng prefix-function pi[i] = độ dài đoạn dài nhất vừa là tiền tố vừa là hậu tố của pat[0..i] (không tính cả chuỗi). Ví dụ với mẫu ABABC:

   pat:   A  B  A  B  C
   chi:   0  1  2  3  4
   pi:    0  0  1  2  0
                  ^ "AB" la tien to & hau to cua "ABA"? -> "A" dai 1
                     ^ "ABAB": tien to=hau to dai nhat = "AB" -> 2
🐞 Xây prefix-function cho mẫu ABABCBước 1/6
1def prefix_function(pat):
2  m = len(pat)
3  pi = [0] * m
4  k = 0
5  for i in range(1, m):
6      while k > 0 and pat[i] != pat[k]:
7          k = pi[k - 1]
8      if pat[i] == pat[k]:
9          k += 1
10      pi[i] = k
11  return pi
Biến tại bước này
pi[0,0,0,0,0]
k0
👉 pi[0] luôn 0. k = độ dài khớp hiện tại.

4. KMP: dùng bảng để quét văn bản một lần​

Khi quét, ta giữ j = số ký tự của mẫu đã khớp. Gặp lệch, thay vì lùi, ta nhảy j = pi[j-1] — trượt mẫu tới vị trí an toàn gần nhất. Con trỏ văn bản i chỉ tiến, không bao giờ lùi → mỗi ký tự văn bản xét đúng một lần → O(n + m).

Đang tải trình chạy code…

5. Rabin-Karp: so cả đoạn bằng một con số​

KMP khôn ngoan về vị trí trượt; Rabin-Karp khôn ngoan về so sánh. Ý tưởng: biến mỗi đoạn con độ dài m thành một con số — mã băm (hash). Hai chuỗi khác nhau gần như luôn cho hash khác nhau, nên ta chỉ cần so một số thay vì m ký tự.

Bí quyết là rolling hash: khi cửa sổ trượt sang phải một bước, ta không tính lại từ đầu mà cập nhật hash trong O(1) — bỏ ký tự bên trái, thêm ký tự bên phải. Coi chuỗi như một số trong cơ số B:

   hash("ABC") = (A*B^2 + B*B^1 + C*B^0) mod M

   truot sang "BCD":
     bo A:    tru A*B^2
     dich:    nhan ca cum cho B
     them D:  cong D

Vì hash có thể trùng dù chuỗi khác (đụng độ — collision), khi hai hash bằng nhau ta vẫn so lại từng ký tự để chắc chắn. Trung bình vẫn O(n + m); xấu nhất O(n·m) nếu xui đụng độ liên tục (hiếm với M nguyên tố lớn).

Đang tải trình chạy code…
Liên hệ với hash table

Rolling hash chính là ý tưởng băm chuỗi thành số mà bạn đã gặp ở bảng băm (hash table). Khác biệt: ở đây ta thiết kế hàm băm sao cho trượt cửa sổ cập nhật được trong O(1), thay vì băm lại từ đầu.

6. So sánh và bẫy thường gặp​

Thuật toánThời gianÝ tưởng then chốtKhi nào chọn
Ngây thơO(n·m)so mọi vị trímẫu/văn bản ngắn, code nhanh
KMPO(n + m)prefix-function, không lùi văn bảnmột mẫu, cần đảm bảo xấu nhất
Rabin-KarpO(n + m) TBrolling hashtìm nhiều mẫu cùng lúc, chuỗi 2D

Bẫy thường gặp:

  • KMP: nhầm pi[j-1] thành pi[j] khi lùi — sai chỉ số là lỗi kinh điển. Luôn lùi về pi[j-1].
  • Rabin-Karp: quên so lại chuỗi khi hash trùng → báo nhầm vị trí do đụng độ. Luôn xác nhận lại.
  • Rabin-Karp: trong Python số nguyên không tràn, nhưng vẫn nên lấy mod để hash gọn và nhất quán.
  • Mẫu rỗng: quyết định quy ước trả về gì (ở đây ta trả về danh sách rỗng).

7. Mẫu nhận diện​

  • "Tìm/đếm số lần một chuỗi con xuất hiện", Ctrl+F, lọc spam theo từ khoá → so khớp mẫu.
  • Cần đảm bảo O(n+m) xấu nhất với một mẫu cố định → KMP.
  • Tìm nhiều mẫu, so khớp chuỗi 2D, hoặc cần so nhanh các đoạn bằng nhau → Rabin-Karp / rolling hash.
  • "Tiền tố cũng là hậu tố", "biên (border) của chuỗi", chu kỳ chuỗi → bảng prefix-function của KMP.

8. 🎮 Trò chơi: So khớp mẫu​

🎮 So khớp mẫuCâu 1/4· Điểm 0· 🔥 0

Naive O(n·m), KMP và Rabin-Karp O(n+m). Nhớ ý tưởng then chốt của từng cái!

prefix_function("ABABC") cho mảng nào?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. pi[i] trong KMP là độ dài của?
2. Rolling hash cho phép cập nhật hash khi trượt cửa sổ trong thời gian?
3. Khi nào Rabin-Karp tỏ ra đặc biệt lợi thế so với KMP?

10. Hoàn thành​

…

☑️ Tiếp theo: Trụ 4 — Mẫu giải bài (các khuôn mẫu giải toán lập trình). (đang biên soạn)