Reverse Factor có một nhược điểm: trên một số mẫu có cấu trúc lặp gần đều (near-periodic), bước dịch cửa sổ sau mỗi lần thử có thể chỉ dài 1, trong khi mỗi lần thử lại phải quét lại gần như toàn bộ cửa sổ trước khi ôtômat "kẹt". Hệ quả là tổng chi phí có thể lên tới O(mn) — chẳng hạn với mẫu dạng "aaa...ab" trên văn bản toàn ký tự a, ở mỗi vị trí cửa sổ, đoạn "tiền tố khớp" gần như luôn được tìm thấy ở những chỉ số rất gần điểm bắt đầu cửa sổ, buộc bước dịch chỉ tiến được 1 ô mỗi lần.
Turbo Reverse Factor khắc phục điều này bằng cách ghi nhớ, sau mỗi lần thử, độ dài của factor vừa khớp được (gọi là bộ nhớ, memory). Ở lần thử kế tiếp, nếu factor khớp được lần này ngắn hơn nhiều so với factor đã ghi nhớ từ lần trước, đó là dấu hiệu cho thấy có thể an toàn để dịch cửa sổ xa hơn mức tối thiểu mà bước dịch thông thường đề xuất — vì phần chênh lệch giữa hai độ dài khớp đã "chứng minh" rằng không có xuất hiện nào của mẫu nằm trong khoảng đó. Cơ chế này (turbo shift) hoàn toàn tương tự ý tưởng dùng trong Turbo Boyer-Moore, chỉ khác là áp dụng cho việc quét factor bằng ôtômat thay vì so sánh ký tự trực tiếp.
Tiền xử lý. Giống hệt Reverse Factor: dựng ôtômat hậu tố (suffix automaton) cho mẫu x đọc ngược, đánh dấu các trạng thái "kết" — những trạng thái nằm trên chuỗi liên kết hậu tố xuất phát từ trạng thái cuối cùng, tương ứng với việc factor vừa đọc cũng là một tiền tố của mẫu gốc.
Tìm kiếm. Duy trì hai biến bổ sung ngoài các biến của Reverse Factor:
u — độ dài factor đã khớp được ở lần thử ngay trước đó (số ký tự đọc được trước khi ôtômat kẹt hoặc khớp trọn mẫu);v cùng bước dịch cơ sở last (tính như Reverse Factor — vị trí nhỏ nhất j mà trạng thái là "kết"), ta tính thêm một bước dịch "turbo": ts = u − v.Bước dịch cuối cùng được chọn là shift = max(last, ts, 1). Trực giác: nếu lần trước ta đã xác nhận một đoạn dài u ký tự là factor của mẫu, còn lần này chỉ khớp được v < u ký tự rồi kẹt, thì phần chênh lệch u − v ký tự ở giữa chắc chắn không thể chứa điểm bắt đầu của một xuất hiện mới mà bước dịch thông thường bỏ sót — nhờ vậy tổng số bước dịch "quá ngắn" liên tiếp bị chặn, giúp tổng chi phí toàn bộ quá trình tìm kiếm còn O(n) trong trường hợp xấu nhất, thay vì O(mn) như Reverse Factor gốc. Biến u sau đó được cập nhật bằng v của lần thử hiện tại để dùng cho lần kế tiếp.
Khi j giảm xuống dưới 0 trong lúc quét (tức toàn bộ cửa sổ đã được đọc mà ôtômat không kẹt), ta ghi nhận một xuất hiện của mẫu tại vị trí cửa sổ hiện tại, giống Reverse Factor.
#include <stdio.h>
#include <string.h>
#define ASIZE 128 /* kich thuoc bang chu cai */
#define XSIZE 256 /* do dai mau toi da */
#define UNDEFINED (-1)
/* O-to-mat hau to (suffix automaton) cua mau dao nguoc */
typedef struct {
int len; /* do dai factor dai nhat cua trang thai */
int link; /* lien ket hau to */
int term; /* 1 neu la trang thai ket (nhan tien to mau) */
int next[ASIZE]; /* ham chuyen */
} SamState;
static SamState sam[2 * XSIZE];
static int samSize, samLast;
static void samInit(void) {
int c;
samSize = 1;
samLast = 0;
sam[0].len = 0;
sam[0].link = UNDEFINED;
sam[0].term = 0;
for (c = 0; c < ASIZE; ++c)
sam[0].next[c] = UNDEFINED;
}
static void samExtend(int c) {
int cur, p, q, clone, i;
cur = samSize++;
sam[cur].len = sam[samLast].len + 1;
sam[cur].term = 0;
for (i = 0; i < ASIZE; ++i)
sam[cur].next[i] = UNDEFINED;
p = samLast;
while (p != UNDEFINED && sam[p].next[c] == UNDEFINED) {
sam[p].next[c] = cur;
p = sam[p].link;
}
if (p == UNDEFINED)
sam[cur].link = 0;
else {
q = sam[p].next[c];
if (sam[p].len + 1 == sam[q].len)
sam[cur].link = q;
else {
clone = samSize++;
sam[clone].len = sam[p].len + 1;
sam[clone].link = sam[q].link;
sam[clone].term = 0;
memcpy(sam[clone].next, sam[q].next, sizeof(sam[q].next));
while (p != UNDEFINED && sam[p].next[c] == q) {
sam[p].next[c] = clone;
p = sam[p].link;
}
sam[q].link = clone;
sam[cur].link = clone;
}
}
samLast = cur;
}
/* Dung o-to-mat hau to cho x dao nguoc va danh dau trang thai ket */
static void buildReverseSam(char *x, int m) {
int i, p;
samInit();
for (i = m - 1; i >= 0; --i) /* nap x tu phai sang trai */
samExtend((unsigned char) x[i]);
p = samLast; /* danh dau cac trang thai ket */
while (p != UNDEFINED) {
sam[p].term = 1;
p = sam[p].link;
}
}
void search(char *x, int m, char *y, int n) {
int pos, j, state, last, v, u, ts, shift;
/* Tien xu ly */
buildReverseSam(x, m);
/* Tim kiem */
pos = 0;
u = 0; /* do dai factor khop lan truoc */
while (pos <= n - m) {
j = m - 1;
state = 0;
last = m; /* buoc dich mac dinh */
while (j >= 0) {
int nstate = sam[state].next[(unsigned char) y[pos + j]];
if (nstate == UNDEFINED)
break; /* otomat ket, dung quet */
state = nstate;
if (sam[state].term && j > 0)
last = j; /* ghi nho tien to dai nhat */
--j;
}
v = m - 1 - j; /* so ky tu da khop lan nay */
if (j < 0) /* doc het cua so: khop */
printf("Khop tai vi tri %d\n", pos);
ts = u - v; /* buoc dich "turbo" tu bo nho */
shift = last;
if (ts > shift)
shift = ts;
if (shift < 1)
shift = 1;
u = v; /* cap nhat bo nho cho lan sau */
pos += shift;
}
}Xét mẫu x = "GCAGAGAG" (m = 8) và văn bản y = "GCATCGCAGAGAGTATACAGTACG" (n = 24), giống ví dụ đã dùng cho Reverse Factor.
y[7..0] ngược lại, ôtômat kẹt sớm (đoạn "...CGCA" không phải factor của mẫu); biến last được cập nhật theo tiền tố dài nhất từng gặp, v là số ký tự đã khớp trước khi kẹt. Vì đây là lần thử đầu tiên, u = 0, nên ts = 0 − v ≤ 0, bước dịch turbo không phát huy tác dụng — cửa sổ dịch theo last như Reverse Factor thông thường. Cập nhật u = v để dùng cho lần sau."GCAGAGAG", ôtômat đi hết 8 ký tự mà không kẹt (j giảm xuống dưới 0). Chương trình in ra "Khop tai vi tri 5".u − v không đủ lớn để vượt qua last, nên hành vi giống hệt Reverse Factor gốc. Sự khác biệt giữa hai thuật toán chỉ bộc lộ rõ trên các mẫu có cấu trúc gần tuần hoàn (ví dụ mẫu dạng "aaa...ab" so khớp trên văn bản có những đoạn dài toàn ký tự a): khi đó, cơ chế bộ nhớ giúp tránh được kiểu dịch chuyển từng-bước-một liên tục vốn gây ra chi phí bậc hai ở Reverse Factor thông thường.