Boyer-Moore 從模式串右端開始比對，利用壞字元規則與好後綴規則實現大幅跳躍，平均 O(n/m)、最壞 O(nm)。
badShift[256]void buildBadShift(const char *pat, int m, int badShift[]) {
for (int c=0; c<256; c++) badShift[c] = m;
for (int i=0; igoodShift[m]void buildGoodShift(const char *pat, int m, int goodShift[]) {
int *suffix = malloc(m * sizeof(int));
// 計算 suffix[i] = 模式串 i 位置開始的最長後綴長度
suffix[m-1] = m;
for (int i=m-2; i>=0; i--) {
int j = i;
while (j >= 0 && pat[j] == pat[m-1 - (i-j)]) j--;
suffix[i] = i - j;
}
// 填表
for (int i=0; i=0; i--) {
if (suffix[i] == i+1) { // 前綴也是後綴
for (; j < m-1-i; j++)
if (goodShift[j] == m) goodShift[j] = m-1-i;
}
}
for (int i=0; i int bmSearch(const char *text, int n, const char *pat, int m) {
int badShift[256], goodShift[m];
buildBadShift(pat, m, badShift);
buildGoodShift(pat, m, goodShift);
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && text[i+j] == pat[j]) j--;
if (j < 0) return i; // 找到
int bc = badShift[(unsigned char)text[i+j]];
int gs = goodShift[j];
i += (bc > gs) ? bc : gs; // 取最大位移
}
return -1;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// ... 上述函數 ...
int main() {
const char *text = "HERE IS A SIMPLE EXAMPLE";
const char *pat = "EXAMPLE";
int pos = bmSearch(text, strlen(text), pat, strlen(pat));
if (pos >= 0) printf("Found at %d\n", pos);
else printf("Not found\n");
return 0;
}suffix 陣列與前綴/後綴匹配邏輯。max(bc, gs) 保證不漏配對。strstr (兩路演算法) 或 memmem 常比手寫 BM 更快，因庫實現高度優化且利用 SIMD。text=aaaaa..., pat=aaab)，實際英文文本極快。Boyer-Moore 是字串匹配算法教科書經典，理解其雙規則跳躍機制，對掌握 KMP、Sunday、Rabin-Karp 等進階算法大有裨益。
