x[1]) trước, rồi mới quay lại so từ đầu nếu ký tự đó khớp.x[0] với x[1] một lần để xác định độ dịch chuyển k và ℓ.y[j+1] trước, rồi nếu khớp mới so x[2], x[3], … và cuối cùng x[0].Brute-force cổ điển so x[0] với y[j] trước; nếu khớp mới so tiếp x[1], x[2], … Nhưng trong thực tế, với bảng chữ cái không quá nhỏ, xác suất x[0] khớp ngẫu nhiên với một ký tự văn bản đã tương đối thấp — brute-force gần như luôn dừng ở phép so đầu tiên. Not So Naive khai thác một quan sát tinh tế hơn: nếu ta biết trước quan hệ giữa x[0] và x[1], ta có thể chọn so sánh ký tự thứ hai của mẫu trước, giúp loại bỏ nhanh hơn các vị trí sai, đồng thời cho phép dịch chuyển 2 vị trí thay vì 1 trong nhiều trường hợp — giảm đáng kể số cửa sổ phải xét trong thực tế, dù độ phức tạp lý thuyết xấu nhất không đổi.
Cụ thể, xét quan hệ giữa hai ký tự đầu mẫu:
x[0] == x[1]: khi x[1] khớp với y[j+1] nhưng x[0] cuối cùng lại không khớp y[j], ta biết chắc cửa sổ tiếp theo (j+1) cũng sẽ thất bại ngay tại vị trí đó (vì y[j+1] đã đối chiếu). Vì vậy có thể dịch 2 khi x[1] khớp, và dịch 2 cả khi x[1] không khớp — chọn k = 2.x[0] != x[1]: khi x[1] không khớp y[j+1], ta chỉ chắc chắn dịch được 1 vị trí; còn khi x[1] khớp thì có thể dịch 2.Điểm mấu chốt: việc kiểm tra x[1] so với y[j+1] trước tiên đóng vai trò một "bộ lọc" rẻ tiền giúp loại nhanh phần lớn các vị trí sai mà không cần bảng tiền xử lý phức tạp.
Tiền xử lý chỉ gồm một phép so sánh: kiểm tra x[0] có bằng x[1] hay không, từ đó ấn định hai hằng số điều khiển dịch chuyển:
x[0] == x[1]: đặt k = 2 (dịch khi x[1] không khớp) và ℓ = 1 (dịch khi toàn bộ so sánh hoàn tất, dù khớp hay không).x[0] != x[1]: đặt k = 1 và ℓ = 2.Pha tìm kiếm, với mỗi vị trí cửa sổ j:
x[1] với y[j+1].k vị trí (không so gì thêm).x[2], x[3], …, x[m-1] với phần văn bản tương ứng; nếu tất cả khớp, so nốt x[0] với y[j] — nếu khớp thì báo tìm thấy tại j. Dù kết quả thế nào, dịch cửa sổ đi ℓ vị trí.Trường hợp m = 1 xử lý riêng: chỉ so từng ký tự văn bản với x[0].
Có thể thấy thuật toán về bản chất vẫn là brute-force nhưng đổi thứ tự và điểm khởi đầu của việc so sánh để tận dụng thông tin rẻ tiền từ hai ký tự đầu mẫu, giúp giảm đáng kể số phép so sánh trung bình trên dữ liệu thực tế mà không phải trả chi phí tiền xử lý nào đáng kể.
#include <stdio.h>
void search(char *x, int m, char *y, int n) {
int i, j, k, ell;
if (m == 1) {
for (j = 0; j < n; ++j)
if (y[j] == x[0])
printf("Tim thay tai vi tri %d\n", j);
return;
}
/* Tiền xử lý: O(1) */
if (x[0] == x[1]) { k = 2; ell = 1; }
else { k = 1; ell = 2; }
/* Tìm kiếm */
j = 0;
while (j + m <= n) {
if (x[1] != y[j + 1])
j += k;
else {
for (i = 2; i < m && x[i] == y[j + i]; ++i);
if (i >= m && x[0] == y[j])
printf("Tim thay tai vi tri %d\n", j);
j += ell;
}
}
}Xét x = "GCAGAGAG" (m = 8) trên y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Vì x[0]=G khác x[1]=C, ta có k = 1, ℓ = 2.
Vài lần thử đầu:
j = 0: so x[1]=C với y[1]=C — khớp. So tiếp x[2..7] với y[2..7]: x[2]=A khớp y[2]=A, nhưng x[3]=G khác y[3]=T — dừng, không khớp toàn bộ. Dịch ℓ = 2.j = 2: so x[1]=C với y[3]=T — khác. Dịch k = 1.j = 3: so x[1]=C với y[4]=C — khớp. So tiếp: x[2]=A khác y[5]=G — dừng. Dịch ℓ = 2.j = 5: so x[1]=C với y[6]=C — khớp. So tiếp toàn bộ x[2..7] với y[7..12], đều khớp; so nốt x[0]=G với y[5]=G — khớp → tìm thấy tại vị trí 5. Dịch ℓ = 2.j = 7: so x[1]=C với y[8]=G — khác. Dịch k = 1.Nhờ so x[1] trước, thuật toán loại nhanh vị trí j = 2 và j = 7 chỉ bằng một phép so sánh, không cần chạm tới x[0].