brBc kích thước σ × σ.Thuật toán Quick Search của Sunday quyết định bước dịch dựa trên ký tự văn bản y[j+m] — ký tự đầu tiên NGAY SAU cửa sổ. Lý do: bất kể cửa sổ hiện tại khớp hay không, mọi lần xuất hiện tiếp theo của mẫu (với bước dịch từ 1 đến m) đều phải "che" vị trí j+m, nên ký tự này luôn cho thông tin dịch hợp lệ.
Berry và Ravindran đẩy ý tưởng này xa thêm một bậc: thay vì chỉ nhìn một ký tự sau cửa sổ, họ nhìn HAI ký tự liền nhau y[j+m] và y[j+m+1]. Cặp hai ký tự mang nhiều thông tin hơn hẳn một ký tự đơn, nên bước dịch trung bình dài hơn — thậm chí có thể đạt tới m + 2 khi cả cặp hoàn toàn không "dính dáng" gì tới mẫu. Bảng brBc[a][b] được tính sẵn trong pha tiền xử lý cho biết cần dịch bao xa cho từng cặp (a, b).
Bảng brBc là bảng hai chiều σ × σ. Với cặp ký tự (a, b) đứng ngay sau cửa sổ, brBc[a][b] là bước dịch nhỏ nhất sao cho sau khi dịch, cặp (a, b) được căn khớp với nội dung mẫu, cụ thể lấy giá trị nhỏ nhất trong các trường hợp:
x[m-1] = a: dịch 1 để ký tự cuối mẫu đè lên vị trí j+m.x[i] = a và x[i+1] = b (0 ≤ i ≤ m-2): căn cặp (a, b) với cặp liền kề trong mẫu.x[0] = b: dịch để ký tự đầu mẫu đè lên vị trí j+m+1.(a, b) không thể nằm trong bất kỳ lần xuất hiện nào chồm qua nó, dịch hẳn qua.Trong cài đặt, ta khởi tạo mọi ô bằng m + 2 rồi lần lượt ghi đè theo thứ tự từ bước dịch lớn đến nhỏ (m + 1, rồi m - i với i tăng dần, cuối cùng là 1), nhờ đó giá trị cuối cùng của mỗi ô đúng bằng giá trị nhỏ nhất.
Pha tìm kiếm rất đơn giản: tại mỗi vị trí cửa sổ j, so khớp mẫu với y[j..j+m-1] (theo bất kỳ thứ tự nào); nếu khớp thì báo. Sau đó — bất kể kết quả — dịch cửa sổ đi brBc[y[j+m]][y[j+m+1]]. Vì công thức dịch đọc tới y[n] và y[n+1] khi cửa sổ chạm cuối văn bản, ta cần hai byte lính canh sau văn bản.
#include <stdio.h>
#include <string.h>
#define ASIZE 256
/* Bảng dịch theo cặp ký tự (y[j+m], y[j+m+1]) */
void preBrBc(char *x, int m, int brBc[ASIZE][ASIZE]) {
int a, b, i;
for (a = 0; a < ASIZE; ++a)
for (b = 0; b < ASIZE; ++b)
brBc[a][b] = m + 2;
for (a = 0; a < ASIZE; ++a)
brBc[a][(unsigned char) x[0]] = m + 1;
for (i = 0; i < m - 1; ++i)
brBc[(unsigned char) x[i]][(unsigned char) x[i + 1]] = m - i;
for (b = 0; b < ASIZE; ++b)
brBc[(unsigned char) x[m - 1]][b] = 1;
}
/* Lưu ý: vùng nhớ của y phải có thêm 2 byte y[n] và y[n+1]. */
void search(char *x, int m, char *y, int n) {
int j;
static int brBc[ASIZE][ASIZE];
/* Tiền xử lý */
preBrBc(x, m, brBc);
y[n] = y[n + 1] = '\0'; /* hai ký tự lính canh */
/* Tìm kiếm */
j = 0;
while (j <= n - m) {
if (memcmp(x, y + j, m) == 0)
printf("Khop tai vi tri %d\n", j);
j += brBc[(unsigned char) y[j + m]][(unsigned char) y[j + m + 1]];
}
}
Xét mẫu x = "GCAGAGAG" (m = 8) và văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).
Một số ô tiêu biểu của bảng brBc: vì x[m-1] = 'G' nên cả hàng brBc[G][*] = 1; cặp (A, G) xuất hiện lần cuối tại x[6..7] nên brBc[A][G] = 2; cặp (C, A) tại x[1..2] cho brBc[C][A] = 7; các cặp (a, G) khác (với a không phải A, G và không tạo cặp trong mẫu) nhận m + 1 = 9; cặp hoàn toàn xa lạ như (T, A) nhận m + 2 = 10.
y[0..7] = "GCATCGCA" với mẫu, thất bại (khác từ vị trí thứ 3). Cặp sau cửa sổ là (y[8], y[9]) = ('G', 'A'), tra brBc[G][A] = 1. Dịch tới j = 1.y[1..8] = "CATCGCAG", thất bại ngay ký tự đầu. Cặp sau cửa sổ (y[9], y[10]) = ('A', 'G'), tra brBc[A][G] = 2. Dịch tới j = 3.y[3..10] = "TCGCAGAG", thất bại. Cặp (y[11], y[12]) = ('A', 'G'), dịch thêm 2 tới j = 5.y[5..12] = "GCAGAGAG", KHỚP toàn bộ, báo một lần xuất hiện tại vị trí 5. Cặp sau cửa sổ (y[13], y[14]) = ('T', 'A'), tra brBc[T][A] = 10, nhảy vọt tới j = 15, bỏ qua cả một vùng chắc chắn không chứa mẫu.