kmpNext có m + 1 phần tử).Cũng như Morris-Pratt, KMP quét văn bản một lượt bằng cửa sổ trượt, so sánh mẫu với văn bản từ trái sang phải, và mỗi khi gặp một điểm lệch (hoặc khớp trọn mẫu) thì trượt cửa sổ đi một đoạn đã tính sẵn sao cho không bao giờ phải quay lui con trỏ trên văn bản.
Điểm khác biệt then chốt nằm ở chỗ: khi xảy ra lệch tại vị trí i của mẫu (tức x[0..i-1] đã khớp nhưng x[i] khác ký tự văn bản), Morris-Pratt chỉ trượt tới biên dài nhất của x[0..i-1]. Nhưng nếu ký tự đầu tiên của phần biên đó lại trùng với x[i], ta biết chắc lần so sánh kế tiếp cũng sẽ lệch với đúng ký tự văn bản vừa gây lệch. KMP loại bỏ trước những lần so sánh vô ích này bằng cách yêu cầu biên phải là biên "mạnh": ký tự đi ngay sau biên phải khác x[i].
Gọi border[i] là độ dài biên dài nhất của x[0..i-1] (biên là chuỗi vừa là tiền tố thực sự vừa là hậu tố thực sự). Bảng của Morris-Pratt lưu chính border[i].
KMP thay bằng bảng kmpNext định nghĩa như sau. Với 0 < i < m:
kmpNext[i] = độ dài biên dài nhất b của x[0..i-1] sao cho x[b] != x[i] (biên "mạnh"); nếu không có biên nào thoả điều kiện thì kmpNext[i] = -1.kmpNext[0] = -1.kmpNext[m] được đặt bằng độ dài biên dài nhất của toàn mẫu (dùng khi mẫu khớp trọn để tiếp tục tìm các lần xuất hiện chồng lấn), không áp thêm điều kiện "mạnh".Bảng kmpNext được tính đệ quy: ta duy trì hai con trỏ i (chạy trên mẫu) và j (độ dài biên hiện tại). Khi x[i] == x[j] ta biết x[0..i] có biên độ dài j+1; lúc đó kiểm tra điều kiện mạnh x[i+1] so với x[j+1] để quyết định sao chép giá trị hay ghi giá trị mới.
Trong pha tìm kiếm, con trỏ i trên mẫu và j trên văn bản cùng tiến. Khi lệch, ta gán i = kmpNext[i] (có thể lặp lại), điều này tương ứng với việc trượt cửa sổ đi i - kmpNext[i] vị trí mà không lùi j.
Giá trị -1 xuất hiện trong bảng cho phép, khi i tụt về -1, cả i và j cùng tăng một bước — tức là bỏ qua ký tự văn bản hiện tại và bắt đầu lại mẫu từ đầu.
#include <stdio.h>
#include <stdlib.h>
void preKmp(char *x, int m, int kmpNext[]) {
int i = 0, j = -1;
kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (i < m && x[i] == x[j])
kmpNext[i] = kmpNext[j]; /* biên "mạnh": sao chép */
else
kmpNext[i] = j;
}
}
void search(char *x, int m, char *y, int n) {
int i, j;
int *kmpNext = (int *) malloc((m + 1) * sizeof(int));
/* Tiền xử lý */
preKmp(x, m, kmpNext);
/* Tìm kiếm */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
printf("Tim thay tai vi tri %d\n", j - i);
i = kmpNext[i];
}
}
free(kmpNext);
}Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Bảng biên mạnh:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| x[i] | G | C | A | G | A | G | A | G | — |
| kmpNext[i] | −1 | 0 | 0 | −1 | 1 | −1 | 1 | −1 | 1 |
Vài bước đầu của pha tìm kiếm:
y[0..2] = "GCA" khớp x[0..2], nhưng x[3]=G lệch với y[3]=T. Vì kmpNext[3] = -1, con trỏ mẫu tụt về −1, cả hai con trỏ cùng tiến: cửa sổ nhảy tới vị trí 4.y[4]=C, so với x[0]=G lệch; kmpNext[0] = -1 nên nhảy sang y[5].y[5]=G trở đi, mẫu khớp liên tiếp x[0..7] với y[5..12], báo tìm thấy tại vị trí 5. Sau đó i = kmpNext[8] = 1, cửa sổ trượt để tận dụng phần đã khớp.Điểm đáng chú ý: nhờ giá trị kmpNext[3] = -1 (biên mạnh), khi lệch tại x[3]=G thuật toán không phí công so lại ký tự G như Morris-Pratt sẽ làm.