字符串匹配算法进阶：Rabin-Karp、Boyer-Moore、Sunday 与 AC 自动机

字符串匹配，说白了就是在一堆文本里找一段特定的模式串。你可能会说：「这不就是 strstr() 吗？」嗯，没错，但当你面对的是几百万行日志、或者一个实时入侵检测系统时，暴力匹配的 O(n*m) 复杂度会让你怀疑人生。

我个人习惯把字符串匹配算法分成两类：单模式匹配和多模式匹配。今天咱们就把这两类里最实用的几个算法掰开揉碎讲清楚。我会结合自己踩过的坑，帮你避开那些教科书上不会写的雷区。

1. Rabin-Karp 算法：用哈希做匹配

Rabin-Karp 的思路很巧妙——它把字符串当成一个数字来处理。比如把 "abc" 看成 1*26² + 2*26¹ + 3*26⁰。这样比较两个字符串是否相等，就变成了比较两个整数是否相等。

我在项目中遇到过一个问题：需要从 10GB 的日志文件里找出所有包含某个错误码的行。如果用暴力匹配，每条日志都要逐字符比较，太慢了。Rabin-Karp 的滚动哈希特性正好派上用场——每次滑动窗口时，只需要 O(1) 时间就能算出新窗口的哈希值。

// Rabin-Karp 核心实现（C语言）
#define BASE 131
#define MOD 1000000007

int rabin_karp(char *text, char *pattern) {
    int n = strlen(text), m = strlen(pattern);
    if (m > n) return -1;
    
    // 计算 pattern 的哈希值
    long long pat_hash = 0, cur_hash = 0, power = 1;
    for (int i = 0; i < m; i++) {
        pat_hash = (pat_hash * BASE + pattern[i]) % MOD;
        cur_hash = (cur_hash * BASE + text[i]) % MOD;
        power = (power * BASE) % MOD;
    }
    
    // 滚动匹配
    for (int i = 0; i <= n - m; i++) {
        if (cur_hash == pat_hash) {
            // 哈希相等时，再逐字符确认（防碰撞）
            if (strncmp(text + i, pattern, m) == 0)
                return i;
        }
        // 滚动更新哈希
        if (i < n - m) {
            cur_hash = (cur_hash * BASE - text[i] * power + text[i + m]) % MOD;
            if (cur_hash < 0) cur_hash += MOD;
        }
    }
    return -1;
}

2. Boyer-Moore 算法：从右往左匹配的智慧

Boyer-Moore 是我个人最喜欢的单模式匹配算法。它的核心思想是：匹配从右往左进行，利用坏字符规则和好后缀规则跳过尽可能多的字符。

你想想看，如果模式串是 "abc"，文本是 "xyzabc"，暴力匹配要从头比到尾。但 BM 算法先看最后一个字符 'c' 和文本的 'z' 比较——不匹配，而且 'z' 在模式串里根本没出现，直接跳过整个模式串长度！

我记得第一次实现 BM 算法时，坏字符表写对了，但好后缀表搞错了方向，导致匹配结果时对时错。调试了整整一个下午才发现是数组索引越界了。

// Boyer-Moore 坏字符表构建
#define MAX_CHAR 256

void build_bad_char(int *bad_char, char *pattern, int m) {
    for (int i = 0; i < MAX_CHAR; i++)
        bad_char[i] = -1;
    for (int i = 0; i < m; i++)
        bad_char[(unsigned char)pattern[i]] = i;
}

int boyer_moore(char *text, char *pattern) {
    int n = strlen(text), m = strlen(pattern);
    int bad_char[MAX_CHAR];
    build_bad_char(bad_char, pattern, m);
    
    int shift = 0;
    while (shift <= n - m) {
        int j = m - 1;
        // 从右向左匹配
        while (j >= 0 && pattern[j] == text[shift + j])
            j--;
        if (j < 0) return shift;  // 匹配成功
        
        // 坏字符规则：跳过多少字符
        int bad_shift = j - bad_char[(unsigned char)text[shift + j]];
        shift += (bad_shift > 0) ? bad_shift : 1;
    }
    return -1;
}

3. Sunday 算法：BM 的简化版

Sunday 算法是 BM 的一个变种，它只关注「坏字符」规则，而且关注的是当前匹配窗口的下一个字符。说白了，就是看模式串后面的那个字符在模式串里有没有出现，来决定跳多远。

为什么 Sunday 比 BM 更容易实现？因为它不需要好后缀表，只需要一个简单的偏移表。我在做嵌入式设备上的字符串匹配时，经常用 Sunday 算法——代码量小，内存占用少，性能也够用。

// Sunday 算法实现
int sunday(char *text, char *pattern) {
    int n = strlen(text), m = strlen(pattern);
    int shift[MAX_CHAR];
    
    // 初始化偏移表：默认跳过 m+1
    for (int i = 0; i < MAX_CHAR; i++)
        shift[i] = m + 1;
    // 模式串中出现的字符，偏移量为 m - i
    for (int i = 0; i < m; i++)
        shift[(unsigned char)pattern[i]] = m - i;
    
    int pos = 0;
    while (pos <= n - m) {
        int i = 0;
        while (i < m && text[pos + i] == pattern[i])
            i++;
        if (i == m) return pos;
        
        // 关键：看下一个字符
        if (pos + m < n)
            pos += shift[(unsigned char)text[pos + m]];
        else
            break;
    }
    return -1;
}

4. AC 自动机：多模式匹配的终极武器

前面讲的都是单模式匹配——一次只找一个模式串。但如果你有 1000 个敏感词需要同时过滤呢？总不能循环 1000 次单模式匹配吧？

AC 自动机（Aho-Corasick）就是解决这个问题的。它把多个模式串构建成一棵 Trie 树，然后加上失败指针（fail 指针），实现一次扫描文本就能找出所有匹配的模式串。

我曾经在一个网络入侵检测系统里用过 AC 自动机。规则库里有 5000 多条攻击特征，如果用单模式匹配，每条数据包都要匹配 5000 次，CPU 直接拉满。换成 AC 自动机后，一次扫描搞定，CPU 占用率从 90% 降到了 15%。

// AC 自动机节点结构
#define MAX_NODES 100000
#define ALPHABET_SIZE 26

typedef struct {
    int next[ALPHABET_SIZE];  // 子节点索引
    int fail;                 // 失败指针
    int output;               // 模式串编号（-1 表示无）
} ACNode;

ACNode nodes[MAX_NODES];
int node_cnt = 1;  // 根节点为 0

// 插入模式串
void ac_insert(char *pattern, int id) {
    int cur = 0;
    for (int i = 0; pattern[i]; i++) {
        int c = pattern[i] - 'a';
        if (!nodes[cur].next[c])
            nodes[cur].next[c] = node_cnt++;
        cur = nodes[cur].next[c];
    }
    nodes[cur].output = id;
}

// 构建失败指针（BFS）
void ac_build() {
    int queue[MAX_NODES], front = 0, rear = 0;
    for (int c = 0; c < ALPHABET_SIZE; c++) {
        if (nodes[0].next[c]) {
            nodes[nodes[0].next[c]].fail = 0;
            queue[rear++] = nodes[0].next[c];
        }
    }
    while (front < rear) {
        int cur = queue[front++];
        for (int c = 0; c < ALPHABET_SIZE; c++) {
            int child = nodes[cur].next[c];
            if (child) {
                int f = nodes[cur].fail;
                while (f && !nodes[f].next[c])
                    f = nodes[f].fail;
                nodes[child].fail = nodes[f].next[c] ? nodes[f].next[c] : 0;
                queue[rear++] = child;
            }
        }
    }
}

// 匹配文本
void ac_search(char *text) {
    int cur = 0;
    for (int i = 0; text[i]; i++) {
        int c = text[i] - 'a';
        while (cur && !nodes[cur].next[c])
            cur = nodes[cur].fail;
        cur = nodes[cur].next[c] ? nodes[cur].next[c] : 0;
        
        // 检查当前节点及失败链上的输出
        int temp = cur;
        while (temp) {
            if (nodes[temp].output != -1)
                printf("匹配到模式串 %d 在位置 %d\n", nodes[temp].output, i);
            temp = nodes[temp].fail;
        }
    }
}

5. 如何选择？一张表说清楚

嗯，到这里四种算法就讲完了。说实话，字符串匹配这块没有绝对的最优，只有最适合你场景的。我个人建议：先搞清楚你的模式串数量、文本长度、内存限制，再选算法。别一上来就上 AC 自动机，杀鸡焉用牛刀？

最后提醒一句：所有算法在实现时都要考虑边界情况——空字符串、模式串比文本长、大小写敏感等等。这些细节我在项目里吃过不少亏，希望你一次就写对。