Trong Boyer-Moore, quy tắc bad-character quyết định bước dịch dựa trên MỘT ký tự văn bản gây ra sự không khớp. Với bảng chữ cái nhỏ, một ký tự đơn lẻ mang ít thông tin nên bước dịch thường ngắn. Zhu và Takaoka nhận xét rằng nếu ta xét ĐỒNG THỜI hai ký tự cuối cùng của cửa sổ hiện tại, ta có nhiều thông tin hơn để quyết định dịch xa hơn.
Cụ thể, thuật toán xây dựng một bảng hai chiều ztBc[a][b] cho biết: nếu hai ký tự áp chót và chót của cửa sổ lần lượt là a và b thì cửa sổ có thể được dịch bao nhiêu để căn cho cặp (a, b) này trùng với một cặp ký tự liền kề trong mẫu. Quy tắc bad-character theo cặp này được kết hợp với quy tắc good-suffix truyền thống của Boyer-Moore để lấy bước dịch lớn hơn.
Thuật toán dùng hai cấu trúc tiền xử lý:
Bảng bad-character theo cặp ztBc. Đây là bảng σ × σ. Với mỗi cặp (a, b), giá trị ztBc[a][b] là khoảng cách dịch nhỏ nhất sao cho cặp ký tự (a, b) được căn thẳng với một cặp ký tự liền kề x[i-1], x[i] trong mẫu. Cách khởi tạo:
ztBc[a][b] = m.a, đặt ztBc[a][x[0]] = m - 1 (trường hợp cặp chỉ căn được với ký tự đầu mẫu).i từ 1 đến m-2, đặt ztBc[x[i-1]][x[i]] = m - 1 - i, ghi lại lần xuất hiện gần cuối nhất của mỗi cặp liền kề trong mẫu.Bảng good-suffix bmGs. Được tính giống hệt Boyer-Moore, dựa trên mảng suff, trong đó suff[i] là độ dài hậu tố chung dài nhất giữa mẫu và tiền tố x[0..i]. Bảng này cho phép dịch dựa trên đoạn hậu tố đã khớp.
Trong pha tìm kiếm, với cửa sổ tại vị trí j, ta so sánh mẫu với văn bản từ phải sang trái. Nếu khớp toàn bộ, báo một lần xuất hiện rồi dịch theo bmGs[0]. Nếu gặp không khớp tại vị trí i, ta lấy bước dịch bằng giá trị lớn nhất trong hai lựa chọn: bmGs[i] (good-suffix) và ztBc[y[j+m-2]][y[j+m-1]] (bad-character theo cặp hai ký tự cuối của cửa sổ). Việc dùng hai ký tự cuối cửa sổ (chứ không phải ký tự tại vị trí không khớp) là điểm mấu chốt: cặp này cố định với mỗi cửa sổ nên tra bảng được ngay, không phụ thuộc vị trí xảy ra không khớp.
#include <stdio.h>
#include <string.h>
#define ASIZE 256
#define XSIZE 128
#define MAX(a, b) ((a) > (b) ? (a) : (b))
/* Bảng bad-character hai chiều của Zhu-Takaoka */
void preZtBc(char *x, int m, int ztBc[ASIZE][ASIZE]) {
int a, b, i;
for (a = 0; a < ASIZE; ++a)
for (b = 0; b < ASIZE; ++b)
ztBc[a][b] = m;
for (a = 0; a < ASIZE; ++a)
ztBc[a][(unsigned char) x[0]] = m - 1;
for (i = 1; i < m - 1; ++i)
ztBc[(unsigned char) x[i - 1]][(unsigned char) x[i]] = m - 1 - i;
}
/* suff[i] = độ dài hậu tố chung dài nhất của x[0..i] và x */
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
f = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
/* Bảng dịch good-suffix như trong Boyer-Moore */
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void search(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE];
static int ztBc[ASIZE][ASIZE];
/* Tiền xử lý */
preZtBc(x, m, ztBc);
preBmGs(x, m, bmGs);
/* Tìm kiếm */
j = 0;
while (j <= n - m) {
i = m - 1;
while (i >= 0 && x[i] == y[i + j])
--i;
if (i < 0) {
printf("Khop tai vi tri %d\n", j);
j += bmGs[0];
} else
j += MAX(bmGs[i],
ztBc[(unsigned char) y[j + m - 2]]
[(unsigned char) y[j + m - 1]]);
}
}
Xét mẫu x = "GCAGAGAG" (m = 8) và văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Bảng good-suffix tính được: bmGs = [7, 7, 7, 2, 7, 4, 7, 1]. Một vài ô đáng chú ý của bảng ztBc: cặp (C, A) xuất hiện tại x[1..2] nên ztBc[C][A] = 5; cặp (A, G) xuất hiện lần cuối tại x[4..5] nên ztBc[A][G] = 2; cặp (G, A) xuất hiện lần cuối tại x[5..6] nên ztBc[G][A] = 1; các cặp (a, G) chưa được gán khác nhận giá trị 7 (căn với ký tự đầu mẫu); cặp không liên quan nhận giá trị 8.
x[7] = 'G' với y[7] = 'A' không khớp ngay tại i = 7. Cặp hai ký tự cuối cửa sổ là (y[6], y[7]) = ('C', 'A'). Bước dịch = max(bmGs[7] = 1, ztBc[C][A] = 5) = 5. Dịch tới j = 5.y[5..12] = "GCAGAGAG" khớp hoàn toàn. Báo một lần xuất hiện tại vị trí 5, rồi dịch theo bmGs[0] = 7, tới j = 12.y[12..19] = "GTATACAG". So từ phải: khớp G, khớp A, rồi không khớp tại i = 5 (x[5] = 'G' với y[17] = 'C'). Bước dịch = max(bmGs[5] = 4, ztBc[y[18]][y[19]] = ztBc[A][G] = 2) = 4. Dịch tới j = 16.So với bad-character đơn ký tự (thường chỉ dịch 1-2 vị trí trên bảng chữ cái 4 ký tự), bad-character theo cặp cho bước dịch trung bình xa hơn rõ rệt.