m không vượt quá số bit trong một từ máy (word); nói chung O(⌈m/w⌉·n) với w là kích thước word.Shift-Or thuộc họ thuật toán "song song bit" (bit-parallelism): nó tận dụng việc một từ máy có thể chứa nhiều bit, và các phép toán bit (dịch, hoặc, và) tác động đồng thời lên tất cả các bit trong một lệnh. Nhờ đó, thuật toán mô phỏng hoạt động của một ôtômat không đơn định nhận diện mẫu, nhưng thực thi song song trên nhiều trạng thái cùng lúc.
Ta duy trì một vector bit R mô tả tình trạng khớp hiện tại: bit thứ i của R cho biết liệu tiền tố x[0..i] có đang khớp với đoạn văn bản kết thúc tại ký tự vừa đọc hay không. Mỗi khi đọc một ký tự văn bản mới, ta cập nhật toàn bộ vector R chỉ bằng hai phép toán bit.
Quy ước bit: ta dùng quy ước "0 nghĩa là đang khớp" (đây là lý do có tên "Shift-Or"). Bit thứ i của R bằng 0 nếu tiền tố độ dài i+1 của mẫu khớp với hậu tố của phần văn bản đã đọc.
Tiền xử lý — mảng mặt nạ S: với mỗi ký tự c của bảng chữ cái, ta tính một mặt nạ bit S[c]. Bit thứ i của S[c] bằng 0 nếu x[i] == c, ngược lại bằng 1. Nói cách khác, S[c] đánh dấu (bằng bit 0) mọi vị trí trong mẫu mà ký tự đúng là c.
Cập nhật: khi đọc ký tự y[j], ta cập nhật vector trạng thái theo công thức:
R = (R << 1) | S[y[j]]Phép dịch trái R << 1 tương ứng với việc "kéo dài" mọi phần khớp thêm một ký tự (và tự động đưa bit 0 vào vị trí thấp nhất, khởi động một phép thử mới từ đầu mẫu). Phép OR với S[y[j]] giữ bit 0 (đang khớp) chỉ tại những vị trí mà ký tự văn bản trùng ký tự mẫu tương ứng.
Phát hiện xuất hiện: mẫu xuất hiện kết thúc tại y[j] khi và chỉ khi bit thứ m-1 của R bằng 0. Ta kiểm tra điều này bằng cách AND với mặt nạ 1 << (m-1).
Vì mọi phép toán trên R là thao tác trên một từ máy, mỗi bước tốn O(1) miễn là m ≤ w. Với mẫu dài hơn word, ta phải dùng nhiều word và chi phí nhân thêm hệ số ⌈m/w⌉.
#include <stdio.h>
#include <limits.h>
#define ASIZE 256
#define WORD_BITS (sizeof(unsigned long) * CHAR_BIT)
void search(char *x, int m, char *y, int n) {
unsigned long S[ASIZE], R, lim;
int i, j;
if (m > (int)WORD_BITS) {
printf("Mau qua dai cho mot tu may\n");
return;
}
/* Tiền xử lý: mặt nạ S[c], bit i = 0 nếu x[i] == c */
for (i = 0; i < ASIZE; i++)
S[i] = ~0UL; /* tất cả bit = 1 */
for (i = 0; i < m; i++)
S[(unsigned char)x[i]] &= ~(1UL << i);
/* lim đánh dấu bit thứ m-1 để phát hiện khớp trọn vẹn */
lim = 1UL << (m - 1);
/* Pha tìm kiếm */
R = ~0UL; /* chưa khớp gì: mọi bit = 1 */
for (j = 0; j < n; j++) {
R = (R << 1) | S[(unsigned char)y[j]];
if ((R & lim) == 0)
printf("Tim thay tai vi tri %d\n", j - m + 1);
}
}Chú ý: khi khởi tạo, R được đặt toàn bit 1 (chưa có phần khớp nào). Phép R << 1 mỗi bước tự đưa một bit 0 vào vị trí 0, tương đương với việc luôn khởi động một phép thử mới bắt đầu từ ký tự đầu của mẫu.
Xét mẫu x = "GCAGAGAG" (m = 8) trên y = "GCATCGCAGAGAGTATACAGTACG". Ta dùng 8 bit thấp của R, bit 0 là bit thấp nhất.
Tiền xử lý — mặt nạ (viết bit 0 ở vị trí ký tự tương ứng, các vị trí mẫu là G C A G A G A G cho index 0..7):
S['G']: mẫu có G tại các vị trí 0, 3, 5, 7 → bit 0 tại các vị trí đó.S['C']: C tại vị trí 1.S['A']: A tại các vị trí 2, 4, 6.T): mặt nạ toàn bit 1 (không có vị trí nào khớp).Duyệt văn bản (bit 0 = đang khớp; ta theo dõi bit thấp nhất trở lên):
y[0]='G': R = (R<<1) | S['G']. Bit 0 của R thành 0 vì x[0]='G' khớp → tiền tố "G" đang khớp.y[1]='C': sau cập nhật, bit 1 thành 0 vì x[1]='C' khớp và bit 0 trước đó đang là 0 → tiền tố "GC" khớp.y[2]='A': bit 2 thành 0 → tiền tố "GCA" khớp.y[3]='T': S['T'] toàn bit 1, mọi phần khớp bị xóa → không tiền tố nào khớp, R trở lại toàn 1 (trừ bit 0 vẫn được reset thử lại). Phần khớp GCA bị hủy vì T không nối tiếp được.Quá trình tiếp tục. Đến khi đọc hết đoạn y[5..12] = "GCAGAGAG", các bit lần lượt được đưa về 0 cho tới bit thứ 7. Tại j = 12, bit thứ m-1 = 7 của R bằng 0, thỏa R & lim == 0, nên báo xuất hiện tại vị trí 12 - 8 + 1 = 5.