m + 1 phần tử.2n - 1.Điểm yếu chí mạng của thuật toán vét cạn là mỗi khi gặp điểm sai lệch, nó vứt bỏ toàn bộ công sức so sánh và bắt đầu lại từ vị trí kế tiếp, khiến nhiều ký tự văn bản bị so sánh nhiều lần. Morris-Pratt khắc phục điều này bằng một nhận xét đơn giản: khi ta đã khớp được một phần đầu của mẫu với văn bản rồi mới gặp sai lệch, ta đã "biết" chính những ký tự văn bản đó (chúng bằng phần mẫu vừa khớp). Ta có thể dùng thông tin này để dịch cửa sổ đi xa mà không cần đọc lại các ký tự văn bản đã đọc.
Cụ thể, sau một sai lệch, thay vì dịch cửa sổ một bước và so lại từ đầu, ta dịch cửa sổ sao cho biên (phần vừa là tiền tố vừa là hậu tố) dài nhất của phần đã khớp được canh lại đúng vị trí. Con trỏ trên văn bản không bao giờ lùi.
Khái niệm biên: một biên của chuỗi u là một chuỗi vừa là tiền tố thực sự, vừa là hậu tố thực sự của u. Ví dụ, chuỗi "abcab" có biên "ab".
Bảng biên mpNext: mảng mpNext[0..m] trong đó mpNext[i] là độ dài của biên dài nhất của tiền tố x[0..i-1] (phần mẫu đã khớp gồm i ký tự đầu). Theo quy ước, mpNext[0] = -1 để xử lý gọn trường hợp sai lệch ngay ký tự đầu.
Ý nghĩa vận hành: giả sử ta đã khớp i ký tự của mẫu rồi gặp sai lệch tại x[i]. Khi đó không cần thử lại từ đầu; ta biết mpNext[i] ký tự đầu của mẫu vẫn đang khớp (vì chúng là biên của phần vừa khớp, nên trùng với phần đuôi văn bản vừa đọc). Ta chỉ việc đặt con trỏ mẫu về vị trí mpNext[i] và tiếp tục so từ đó, không dịch chuyển con trỏ văn bản.
Xây bảng biên cũng chính là bài toán so khớp mẫu với chính nó, thực hiện trong O(m):
i = 0, j = mpNext[0] = -1
lặp i từ 0 đến m-1:
trong khi j > -1 và x[i] != x[j]: j = mpNext[j]
i++, j++
mpNext[i] = jPha tìm kiếm: dùng cùng cơ chế con trỏ. Duy trì con trỏ j chỉ vào mẫu; duyệt văn bản bằng con trỏ i. Khi x[j] khác y[i], ta lùi j theo bảng biên (j = mpNext[j]) cho tới khi khớp lại hoặc j = -1. Khi j đạt m, ta báo một xuất hiện rồi tiếp tục lùi j theo bảng biên để tìm xuất hiện chồng lấn tiếp theo.
Vì con trỏ văn bản i chỉ tăng, và mỗi lần lùi j tương ứng với một lần j đã tăng trước đó, tổng số thao tác bị chặn tuyến tính; số phép so sánh ký tự trong pha tìm kiếm tối đa là 2n - 1.
#include <stdio.h>
#include <stdlib.h>
/* Tiền xử lý: xây bảng biên mpNext[0..m] */
void preMp(char *x, int m, int mpNext[]) {
int i, j;
i = 0;
j = mpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = mpNext[j];
i++;
j++;
mpNext[i] = j;
}
}
void search(char *x, int m, char *y, int n) {
int i, j;
int *mpNext = malloc((m + 1) * sizeof(int));
/* Tiền xử lý */
preMp(x, m, mpNext);
/* Pha tìm kiếm */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = mpNext[i];
i++;
j++;
if (i >= m) {
printf("Tim thay tai vi tri %d\n", j - i);
i = mpNext[i];
}
}
free(mpNext);
}Ở đây i là con trỏ trên mẫu, j là con trỏ trên văn bản (luôn tăng). Mỗi khi i đạt m, ta in vị trí bắt đầu j - i rồi lùi i về mpNext[i] để tiếp tục.
Xét mẫu x = "GCAGAGAG" (m = 8).
Bảng biên mpNext cho mẫu này:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| x[i] | G | C | A | G | A | G | A | G | |
| mpNext[i] | -1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
Ví dụ, tiền tố "GCAG" (i = 4) có biên dài nhất là "G" độ dài 1, nên mpNext[4] = 1.
Tìm kiếm trên y = "GCATCGCAGAGAGTATACAGTACG":
Bắt đầu i = 0, j = 0. So khớp x[0..2] = "GCA" với y[0..2] = "GCA" thành công, i và j cùng tăng tới i = 3, j = 3. Tại đây x[3]='G' khác y[3]='T' → sai lệch. Ta lùi i = mpNext[3] = 0. Vì x[0]='G' vẫn khác y[3]='T', lùi tiếp i = mpNext[0] = -1, rồi i++, j++ thành i = 0, j = 4.
Điểm quan trọng: con trỏ văn bản j không hề lùi — ta không so lại y[0..2]. Đây chính là ưu điểm so với vét cạn.
Tiếp tục: tại j = 4 (y[4]='C'), x[0]='G' khác nên i giữ ở 0, j tăng lên 5. Từ j = 5, đoạn y[5..12] = "GCAGAGAG" khớp toàn bộ mẫu; i tăng dần tới i = 8 khi j = 13. Lúc i đạt m = 8, ta báo xuất hiện tại vị trí j - i = 13 - 8 = 5, rồi lùi i = mpNext[8] = 1 để tiếp tục tìm.