Bài toán: Cho 2 xâu A và B. Hãy tìm các vị trí trên xâu A mà nó khớp với xâu B.
Ví dụ: với A = "aaaaa", B = "aa", thì các vị trí tìm được là 1, 2, 3, 4 (giả định là ta đang dùng hệ đếm từ 1).
Đây là hướng dẫn sử dụng thuật toán KMP để giải quyết bài toán trên. Thuật toán KMP cải tiến từ phương pháp khờ khạo có độ phức tạp O(|A|*|B|).
Cách tiếp cận của thuật toán KMP là khởi tạo sẵn các thông tin về xâu B và sử dụng kỹ thuật 2-con-trỏ (two pointers). Việc này giúp giảm thiểu việc xét lại các vị trí đã được duyệt qua.
Khởi tạo thông tin về xâu B Trước hết, ta cần hiểu rõ các thông tin cần thiết để giải quyết bài toán.
Việc chậm chạp của phương pháp khờ khạo xảy ra khi bắt đầu có một vị trí trên xâu A mà khớp với xâu B. Từ vị trí này trở về sau, phương pháp khờ khạo yêu cầu ta phải xét lại từng vị trí phía sau, trong khi có nhiều trường hợp ta có thể bỏ qua.
Việc ta cần làm ở đây là:
- Đầu tiên, giả định là mọi số thứ tự ở đây thuộc hệ đếm mà phần tử đầu tiên có thứ tự 1.
- Với mỗi vị trí thứ i trên xâu B, ta cần biết giá trị k (0 = k = i) thoả mãn:
- Tiền tố độ dài k của B và hậu tố độ dài k của B{i} là hai xâu bằng nhau.
- Giá trị của k phải là lớn nhất có thể.
Việc xây dựng xâu LPS[] (LPS là viết tắt cho Longest Proper Suffix - hậu tố đúng dài nhất) để lưu các giá trị này. Ta xét một số ví dụ với các xâu B khác nhau:
- B = "AAAA" => LPS[] = {0, 1, 2, 3}
- B = "ABCDE" => LPS[] = {0, 0, 0, 0, 0}
- B = "AABAACAABAA" => LPS[] = {0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5}
Việc duyệt xâu A Việc áp dụng kỹ thuật 2-con-trỏ để xử lý xâu A tương tự như cách xử lý xâu B.
Ta đặt biến tạm tmp = 0 rồi bắt đầu duyệt từ đầu xâu A. Chừng nào B[tmp] và A[i] chưa khớp nhau và tmp còn mang giá trị dương, ta giảm giá trị tmp xuống.
Có 2 trường hợp xảy ra:
- Nếu B[tmp] đã khớp với A[i], tức là ta đã tìm được hậu tố đúng thỏa mãn ở vị trí i. Ta tăng giá trị tmp thêm 1 đơn vị.
- Nếu hậu tố độ dài |B| của A{i} đã khớp hoàn toàn với xâu B, ta lưu lại vị trí đúng. Vị trí đầu sẽ là (i - |B| + 1).
- Đẩy xâu B sao cho một phần của B nằm bên phải cây kim, tức là tìm tiền tố đúng của B còn khớp với hậu tố tương ứng của A{i}.
- Nếu không, tức là tmp = 0, và không có tiền tố nào của B khớp với hậu tố tương ứng cùng độ dài của xâu A{i}. Ta bỏ qua và duyệt tiếp tới i tiếp theo.
Độ phức tạp của cả quá trình là O(|A|+|B|) (tuyến tính).
Bài tập code: VNSPOJ-SUBSTR Code mẫu: Ideone.com
Một số nội dung được sử dụng từ sách Competitive Programming 3 của Steven Halim, NUS, Singapore.