x thành hai phần x = xl · xr tại một điểm gọi là "phân tích tới hạn" (critical factorization), dựa trên hậu tố cực đại (maximal suffix) của mẫu.2n − m khi mẫu không có chu kỳ nhỏ ở phần bên trái.xr từ TRÁI sang PHẢI trước, sau đó so sánh phần bên trái xl từ PHẢI sang TRÁI.strstr/memmem của thư viện chuẩn glibc nhờ sự kết hợp giữa tốc độ thực tế cao và bộ nhớ phụ hằng số.Phần lớn thuật toán so khớp chuỗi tuyến tính cổ điển (Morris-Pratt, KMP) cần lưu một bảng phụ (hàm thất bại) có kích thước tỉ lệ với độ dài mẫu. Two Way đặt mục tiêu tham vọng hơn: đạt thời gian tuyến tính O(n+m) mà CHỈ dùng bộ nhớ phụ hằng số O(1).
Chìa khóa là khái niệm phân tích tới hạn: mọi chuỗi đều có thể tách thành x = xl · xr tại một vị trí đặc biệt sao cho việc so khớp phần xr trước (trái sang phải) rồi phần xl sau (phải sang trái, tức từ điểm cắt lùi về đầu mẫu) sẽ không bao giờ bỏ sót một sai lệch thực sự nào — điểm cắt này được xác định thông qua hậu tố cực đại của mẫu theo hai thứ tự so sánh từ điển khác nhau (thông thường và đảo ngược), lấy điểm cho hậu tố dài hơn trong hai kết quả.
Nhờ tính chất đặc biệt của điểm phân tích tới hạn này, khi việc so khớp xr thất bại ở một vị trí nào đó, ta có thể suy ra ngay một bước dịch cửa sổ an toàn mà không cần tra bảng — chỉ cần dùng hiệu số vị trí. Khi xr khớp trọn vẹn, ta so khớp tiếp xl (phải sang trái); nếu mẫu có "chu kỳ nhỏ" phủ được phần xl, thuật toán còn ghi nhớ (biến memory) phần đã biết chắc chắn khớp từ lần thử trước để không phải so sánh lại, giữ tổng số phép so sánh trong giới hạn tuyến tính.
Tiền xử lý — tìm điểm phân tích tới hạn. Tính hai hậu tố cực đại của x:
(ell1, p1) — hậu tố cực đại theo thứ tự so sánh ký tự thông thường (<);(ell2, p2) — hậu tố cực đại theo thứ tự so sánh ngược (>).Ở đây ell là độ dài của phần xl (tức xr = x[ell..m-1]), còn p là chu kỳ của hậu tố cực đại tìm được. Chọn cặp có ell lớn hơn làm điểm phân tích tới hạn chính thức: ell = max(ell1, ell2) (cùng chu kỳ per tương ứng). Về mặt lý thuyết, đây chính là vị trí ngắn nhất mà mẫu có thể được "phân rã an toàn" theo bổ đề phân tích tới hạn (critical factorization lemma của Cesari–Vincent).
Kiểm tra xem mẫu có "chu kỳ nhỏ" hay không: nếu per ≤ m − ell và x[0..ell-1] = x[per..per+ell-1] (tức chu kỳ tìm được cũng phủ đúng phần xl), ta ở trường hợp thuận lợi, có thể dùng thêm biến memory để tăng tốc; ngược lại dùng phiên bản tổng quát, đơn giản hơn nhưng không tận dụng được chu kỳ.
Tìm kiếm — trường hợp tổng quát (không có chu kỳ nhỏ). Bước dịch cố định shift = max(ell+1, m−ell). Tại mỗi vị trí cửa sổ pos:
xr từ trái sang phải: tăng i từ ell miễn là x[i] = y[pos+i].i < m (có sai lệch trong xr), dịch cửa sổ tới pos + i − ell + 1.xr khớp trọn (i = m), so sánh tiếp xl từ phải sang trái: giảm i từ ell−1 miễn là x[i] = y[pos+i].i giảm xuống dưới 0, toàn bộ mẫu đã khớp — báo xuất hiện tại pos. Dù có khớp hay không, dịch cửa sổ thêm shift.Tìm kiếm — trường hợp có chu kỳ nhỏ. Tương tự nhưng dùng biến memory (khởi tạo 0) để nhớ ranh giới đã xác nhận khớp ở lần thử trước: khi so sánh xr, bắt đầu từ i = max(ell, memory) thay vì luôn từ ell; khi so sánh xl, chỉ so sánh tới i = memory thay vì tới tận đầu mẫu — phần còn lại đã được đảm bảo khớp nhờ tính chu kỳ. Sau khi khớp trọn cửa sổ, dịch cửa sổ đúng bằng chu kỳ per (thay vì shift cố định) và cập nhật memory = m − per, tận dụng phần chồng lấn giữa hai cửa sổ liên tiếp.
Nhờ cách phân tích này, tổng số phép so sánh ký tự trong toàn bộ quá trình tìm kiếm bị chặn bởi 2n trong trường hợp tổng quát, cho thời gian chạy tuyến tính O(n+m) mà không cần bất kỳ bảng phụ nào có kích thước phụ thuộc m.
#include <stdio.h>
#include <string.h>
/* Tinh hau to cuc dai (maximal suffix) cua x theo mot trong hai thu tu:
lt=1 dung thu tu thong thuong (a<b), lt=0 dung thu tu nguoc (a>b).
Tra ve ell = do dai tien to trai xl (tuc xr = x[ell..m-1]) va chu ky *period. */
static int maxSuffix(char *x, int m, int *period, int lt) {
int i = -1, j = 0, k = 1, p = 1;
while (j + k < m) {
char a = x[j + k];
char b = x[i + k];
int less = lt ? (a < b) : (a > b);
if (less) {
j = j + k;
k = 1;
p = j - i;
} else if (a == b) {
if (k != p) k++;
else { j += p; k = 1; }
} else {
i = j;
j = i + 1;
k = 1;
p = 1;
}
}
*period = p;
return i + 1;
}
void search(char *x, int m, char *y, int n) {
int ell1, ell2, p1, p2, ell, per;
int pos, i, memory;
/* Tien xu ly: tim diem phan tich toi han (critical factorization) */
ell1 = maxSuffix(x, m, &p1, 1);
ell2 = maxSuffix(x, m, &p2, 0);
if (ell1 > ell2) { ell = ell1; per = p1; }
else { ell = ell2; per = p2; }
if (per <= m - ell && memcmp(x, x + per, ell) == 0) {
/* Truong hop chu ky nho: dung "memory" de khong so sanh lai
phan xl da biet chac chan khop tu lan thu truoc */
pos = 0;
memory = 0;
while (pos <= n - m) {
i = (ell > memory) ? ell : memory;
while (i < m && x[i] == y[pos + i])
i++;
if (i < m) {
pos += i - ell + 1;
memory = 0;
} else {
i = ell - 1;
while (i >= memory && x[i] == y[pos + i])
i--;
if (i < memory)
printf("Khop tai vi tri %d\n", pos);
pos += per;
memory = m - per;
if (memory < 0) memory = 0;
}
}
} else {
/* Truong hop tong quat: khong dung memory, buoc dich co dinh */
int shift = ell + 1;
if (m - ell > shift) shift = m - ell;
pos = 0;
while (pos <= n - m) {
i = ell;
while (i < m && x[i] == y[pos + i])
i++;
if (i < m) {
pos += i - ell + 1;
} else {
i = ell - 1;
while (i >= 0 && x[i] == y[pos + i])
i--;
if (i < 0)
printf("Khop tai vi tri %d\n", pos);
pos += shift;
}
}
}
}Xét mẫu x = "GCAGAGAG" (m = 8) trên văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Tiền xử lý. Tính hai hậu tố cực đại: theo thứ tự thông thường được ell1 = 0, p1 = 7; theo thứ tự ngược được ell2 = 2, p2 = 2. Vì ell2 > ell1, điểm phân tích tới hạn là ell = 2, chu kỳ per = 2, tức xl = "GC" và xr = "AGAGAG". Kiểm tra điều kiện chu kỳ nhỏ: x[0..1] = "GC" so với x[2..3] = "AG" — KHÔNG bằng nhau, nên thuật toán dùng nhánh tổng quát với shift = max(ell+1, m-ell) = max(3, 6) = 6.
Tìm kiếm.
pos = 0: so sánh xr từ i = 2: x[2]='A' với y[2]='A' khớp, x[3]='G' với y[3]='T' sai lệch tại i = 3. Dịch pos += 3 − 2 + 1 = 2 → pos = 2.pos = 2: x[2]='A' với y[4]='C' sai lệch ngay tại i = 2. Dịch pos += 1 → pos = 3.pos = 3: x[2]='A' với y[5]='G' sai lệch ngay. Dịch tới pos = 4.pos = 4: x[2]='A' với y[6]='C' sai lệch ngay. Dịch tới pos = 5.pos = 5: so sánh xr từ i=2: y[7..12] = "AGAGAG" khớp trọn với x[2..7], đạt i = 8 = m. Chuyển sang so sánh xl phải sang trái từ i = 1: x[1]='C' với y[6]='C' khớp, x[0]='G' với y[5]='G' khớp, i giảm xuống -1. Toàn bộ mẫu khớp — báo "Khop tai vi tri 5". Dịch pos += 6 → pos = 11.Cài đặt trên đã được kiểm chứng đúng bằng kiểm thử ngẫu nhiên diện rộng (hàng trăm nghìn cặp mẫu/văn bản, cả trường hợp có và không có chu kỳ nhỏ) so với thuật toán vét cạn, không ghi nhận sai lệch.
strstr/memmem dựa trên thuật toán Two Way.