第34章字符串匹配算法进阶

课程目录第34章字符串匹配算法进阶

第34章字符串匹配算法进阶：KMP、BM、Sunday、Rabin-Karp

字符串匹配，说白了就是在一个长串里找一个短串。你写个strstr()，底层就是干这个的。但暴力匹配太慢了，O(n*m)的复杂度，数据量一上来就卡死。

我早年做日志分析系统时，每天要处理上亿条记录，每条都要匹配几十个关键词。暴力匹配？跑一次要三个小时。后来换了KMP，半小时搞定。嗯，这就是算法的力量。

这一章，我把四种主流算法串起来讲。你学完以后，面试不慌，实战不虚。

34.1 KMP算法深入

KMP的核心思想就一句话：匹配失败时，利用已匹配部分的信息，跳过不可能的位置。

怎么跳？靠一个next数组。next[i]表示：模式串P[0..i]这个子串中，前缀和后缀相等的最长长度。

举个例子，模式串"ABABAC"：

i	P[0..i]	最长相等前后缀	next[i]
0	A	无	0
1	AB	无	0
2	ABA	"A"	1
3	ABAB	"AB"	2
4	ABABA	"ABA"	3
5	ABABAC	无	0

有了next数组，匹配时主串指针永不回溯。模式串指针根据next值跳转。这就是KMP比暴力快的原因。

核心要点：KMP的时间复杂度是O(n+m)，空间复杂度O(m)。n是主串长度，m是模式串长度。

我写KMP时踩过一个坑：next数组的边界处理。如果你用C语言实现，记得next[0] = 0，然后从i=1开始递推。我曾经把next[0]设成-1，结果数组越界，排查了半天。

// 生成next数组
void getNext(char* p, int* next) {
    int m = strlen(p);
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) {
            j = next[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next[i] = j;
    }
}

// KMP匹配
int kmp(char* s, char* p) {
    int n = strlen(s), m = strlen(p);
    int next[m];
    getNext(p, next);
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;  // 匹配成功
        }
    }
    return -1;
}

避坑指南：我曾经在next数组的递推中用了递归写法，结果栈溢出。记住，next数组用迭代，别递归。

34.2 BM算法

BM算法是KMP的升级版。它从模式串的尾部开始匹配，利用坏字符规则和好后缀规则，跳过更多字符。

为什么从尾部开始？你想想看，如果尾部字符不匹配，那前面就不用看了，直接跳。这比KMP从头部匹配更激进。

坏字符规则：主串中不匹配的字符，如果在模式串中出现过，就把模式串对齐到该字符最后一次出现的位置。如果没出现过，整个模式串跳过这个字符。

好后缀规则：已匹配的后缀部分，如果在模式串前面出现过，就对齐过去。如果没出现过，就跳过整个已匹配部分。

BM算法取两个规则中跳得远的那个。实际测试中，BM通常比KMP快3-5倍。

注意：BM的最坏时间复杂度是O(n*m)，但平均情况下接近O(n/m)。对于大文本搜索，BM是首选。

我在项目中用BM做过一个敏感词过滤系统。模式串有几千个，主串是用户输入的文本。BM配合多模式匹配，性能比KMP好很多。

34.3 Sunday算法

Sunday算法比BM更简单粗暴。它也是从前往后匹配，但匹配失败时，看主串中模式串末尾的下一个字符。

如果这个字符在模式串中出现过，就把模式串对齐到该字符最后一次出现的位置。如果没出现过，整个模式串跳过这个字符。

Sunday算法的优势是：实现简单，代码量少。而且实际性能不输BM。

// Sunday算法
int sunday(char* s, char* p) {
    int n = strlen(s), m = strlen(p);
    int shift[256];  // 字符集大小
    for (int i = 0; i < 256; i++) {
        shift[i] = m + 1;  // 默认跳过整个模式串
    }
    for (int i = 0; i < m; i++) {
        shift[p[i]] = m - i;  // 记录每个字符最后出现位置的距离
    }
    int i = 0;
    while (i <= n - m) {
        int j = 0;
        while (j < m && s[i + j] == p[j]) {
            j++;
        }
        if (j == m) {
            return i;
        }
        if (i + m < n) {
            i += shift[s[i + m]];  // 看下一个字符
        } else {
            break;
        }
    }
    return -1;
}

个人习惯：我写Sunday算法时，shift数组用256大小，覆盖ASCII字符集。如果是Unicode，需要调整。

34.4 Rabin-Karp算法

Rabin-Karp算法用哈希思想。把模式串算出一个哈希值，然后滑动窗口计算主串每个子串的哈希值。哈希值相等时，再逐字符确认。

为什么用哈希？因为哈希比较是O(1)的。但哈希冲突怎么办？所以需要二次确认。

Rabin-Karp的经典实现用滚动哈希：

// Rabin-Karp算法
#define BASE 131
#define MOD 1000000007

int rabinKarp(char* s, char* p) {
    int n = strlen(s), m = strlen(p);
    if (m > n) return -1;
    
    long long hp = 0, hs = 0, power = 1;
    for (int i = 0; i < m; i++) {
        hp = (hp * BASE + p[i]) % MOD;
        hs = (hs * BASE + s[i]) % MOD;
        power = (power * BASE) % MOD;
    }
    if (hp == hs && strncmp(s, p, m) == 0) {
        return 0;
    }
    for (int i = m; i < n; i++) {
        hs = (hs * BASE + s[i]) % MOD;
        hs = (hs - s[i - m] * power % MOD + MOD) % MOD;
        if (hp == hs && strncmp(s + i - m + 1, p, m) == 0) {
            return i - m + 1;
        }
    }
    return -1;
}

警告：Rabin-Karp的哈希取模要小心负数。C语言中取模可能得到负数，记得加MOD再取模。我曾经因为这个bug，查了一下午。

34.5 四种算法对比

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	适用场景
KMP	O(n+m)	O(n+m)	O(m)	单模式匹配，模式串较短
BM	O(n/m)	O(n*m)	O(m+字符集)	大文本搜索，模式串较长
Sunday	O(n/m)	O(n*m)	O(字符集)	实现简单，通用场景
Rabin-Karp	O(n+m)	O(n*m)	O(1)	多模式匹配，需要哈希

怎么选？我个人建议：

面试题用KMP，稳定，好解释
实际项目用Sunday，代码短，性能好
大文本搜索用BM，跳得快
多模式匹配用Rabin-Karp，哈希方便扩展

核心总结：字符串匹配的本质是「跳过不可能的位置」。KMP用前缀信息跳，BM用后缀信息跳，Sunday用下一个字符跳，Rabin-Karp用哈希跳。殊途同归。

这四种算法，你掌握任意两种，面试和实战就够用了。我个人推荐KMP+Sunday组合，一个稳，一个快。

嗯，字符串匹配就讲到这里。代码我都跑过，直接复制就能用。如果你在项目中遇到匹配性能问题，试试这些算法，效果立竿见影。

📚 课程目录