<, =, >.Phần lớn các thuật toán tuyến tính (Knuth-Morris-Pratt, Boyer-Moore và các biến thể) đều cần một bước tiền xử lý mẫu để dựng bảng dịch, và bảng này chiếm bộ nhớ tỉ lệ với độ dài mẫu hoặc kích thước bảng chữ. Câu hỏi tự nhiên là: liệu có thể đạt thời gian tuyến tính mà chỉ dùng bộ nhớ phụ hằng số hay không?
Thuật toán của Crochemore trả lời khẳng định cho câu hỏi này, với giả thiết duy nhất là bảng chữ có quan hệ thứ tự. Chìa khoá là khái niệm maximal suffix (hậu tố cực đại theo thứ tự từ điển) của đoạn văn bản vừa khớp. Thay vì tra một bảng dựng sẵn, mỗi khi xảy ra sai lệch thuật toán dùng cấu trúc chu kỳ của maximal suffix để quyết định dịch cửa sổ bao xa và bảo toàn được bao nhiêu ký tự đã so — tất cả tính được tăng dần khi cửa sổ trượt.
Với một xâu w, maximal suffix là hậu tố lớn nhất của w theo thứ tự từ điển. Điều quan trọng là maximal suffix có một chu kỳ p xác định rõ cấu trúc lặp của nó; chính chu kỳ này cho biết ta có thể dịch cửa sổ an toàn bao nhiêu bước.
Thuật toán duy trì bốn đại lượng khi phân tích đoạn đã khớp:
i — vị trí bắt đầu của maximal suffix hiện tại;j — vị trí đang xét;k — độ lệch trong lần so sánh nội bộ đang tiến hành;p — chu kỳ hiện tại của maximal suffix.Hàm nextMaximalSuffix mở rộng phân tích thêm một ký tự mỗi lần được gọi, dựa hoàn toàn vào việc so sánh thứ tự giữa hai ký tự a = w[i+k] và b = w[j+k]:
a == b: hai ký tự bằng nhau, nếu k đạt tới chu kỳ p thì tiến j thêm p và đặt lại k = 1, ngược lại tăng k;a > b: ta tìm được một hậu tố lớn hơn, dời j lên và cập nhật chu kỳ p = j - i;a < b: điểm bắt đầu maximal suffix dời sang j, khởi động lại k = p = 1.Trong pha tìm kiếm, tại mỗi vị trí cửa sổ j ta so ký tự mẫu với văn bản từ trái sang phải cho tới khi hết mẫu (tìm được một xuất hiện) hoặc gặp sai lệch tại độ lệch i. Sau đó thuật toán gọi nextMaximalSuffix trên đoạn văn bản y[j..j+i] vừa khớp. Nếu đoạn đã khớp có chu kỳ đẹp, ta dịch cửa sổ đúng p bước và giữ lại i - p ký tự đã khớp; ngược lại ta dịch xa hơn và bắt đầu lại phần so sánh. Việc luôn giữ lại được thông tin về phần đã khớp chính là lý do tổng số phép so sánh vẫn tuyến tính dù không dùng bảng nào.
#include <stdio.h>
#include <string.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
/* Mở rộng phân tích maximal suffix của xâu x[0..m-1] thêm các ký tự,
chỉ dùng so sánh thứ tự (<, =, >) giữa các ký tự. */
void nextMaximalSuffix(char *x, int m,
int *i, int *j, int *k, int *p) {
char a, b;
while (*j + *k < m) {
a = x[*i + *k];
b = x[*j + *k];
if (a == b) {
if (*k == *p) { /* hết một chu kỳ */
*j += *p;
*k = 1;
} else
++(*k);
} else if (a > b) { /* tìm được hậu tố lớn hơn */
*j += *k;
*k = 1;
*p = *j - *i;
} else { /* a < b: dời điểm bắt đầu */
*i = *j;
++(*j);
*k = *p = 1;
}
}
}
void search(char *x, int m, char *y, int n) {
int i, ip, j, jp, k, p;
/* Không có bước tiền xử lý mẫu; mọi thứ tính trong lúc chạy. */
ip = -1;
i = j = jp = 0;
k = p = 1;
while (j <= n - m) {
/* So mẫu với cửa sổ từ trái sang phải */
while (i + j < n && i < m && x[i] == y[i + j])
++i;
if (i == 0) {
++j;
ip = -1;
jp = 0;
k = p = 1;
} else {
if (i >= m)
printf("Tim thay tai vi tri %d\n", j);
/* Phân tích maximal suffix của đoạn văn bản vừa khớp */
nextMaximalSuffix(y + j, i + 1, &ip, &jp, &k, &p);
if (ip < 0 ||
(ip < p && memcmp(y + j, y + j + p, ip + 1) == 0)) {
j += p; /* dịch theo chu kỳ, giữ phần đã khớp */
i -= p;
if (i < 0)
i = 0;
if (jp - ip > p)
jp -= p;
else {
ip = -1;
jp = 0;
k = p = 1;
}
} else {
j += (MAX(ip + 1, MIN(i - ip - 1, jp + 1)) + 1);
i = jp = 0;
ip = -1;
k = p = 1;
}
}
}
}Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Vị trí cửa sổ j = 0: so x[0]=G với y[0]=G khớp, x[1]=C với y[1]=C khớp, x[2]=A với y[2]=A khớp, rồi x[3]=G với y[3]=T sai lệch tại i = 3. Đoạn đã khớp là "GCA". Thuật toán phân tích maximal suffix của "GCA": các ký tự đều khác nhau nên chu kỳ p bằng đúng độ dài, cửa sổ được dịch tới ngay sau vùng không lặp.
Vị trí cửa sổ j = 5: so x[0..7] với y[5..12] = "GCAGAGAG". Lần lượt G-G, C-C, A-A, G-G, A-A, G-G, A-A, G-G đều khớp, i đạt m = 8. Tìm thấy xuất hiện tại vị trí 5. Đoạn đã khớp "GCAGAGAG" có phần lặp AG, cho chu kỳ nhỏ; thuật toán tận dụng chu kỳ này để dịch mà không phải so lại từ đầu.
Sau đó cửa sổ trượt hết phần còn lại "TATACAGTACG" và không tìm thấy xuất hiện nào khác. Tổng số phép so sánh trên toàn bộ quá trình vẫn tuyến tính theo n.