7. 串的模式匹配：从暴力到KMP的进化之路

模式匹配，说白了就是在一个长字符串里找一段短字符串。你在文本编辑器里按Ctrl+F，就是在做这件事。我当年刚学这个知识点时，觉得不就是个查找吗？后来在嵌入式项目里处理通信协议帧，才发现这里面的门道深着呢。

7.1 串的定长顺序存储

先说说串怎么存。嵌入式系统里，动态内存分配是个奢侈品，所以我们常用定长数组。我个人习惯这样定义：

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];   // 存储字符
    int length;        // 当前长度
} SString;

注意，ch[0]我通常闲置不用，从ch[1]开始存数据。为什么？因为这样字符的位置和数组下标就对应上了，KMP算法里用起来特别顺手。你想想看，要是从0开始，next数组的计算还得来回换算下标，多麻烦。

7.2 BF暴力匹配算法

BF算法，全称Brute-Force，暴力匹配。思路简单到令人发指：从主串的第一个字符开始，拿着模式串一个一个比，不行就往后挪一位，再比。

int BF(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++; j++;
        } else {
            i = i - j + 2;  // 回溯
            j = 1;
        }
    }
    if (j > T.length) return i - T.length;
    else return 0;
}

这段代码我闭着眼都能写出来。但你要注意那个回溯的公式：i = i - j + 2。说白了就是：i回到这次匹配的起始位置，再往后挪一位。很多初学者在这里容易搞混，我建议你拿笔在纸上画一画。

BF算法的时间复杂度是O(n*m)，n是主串长度，m是模式串长度。最坏情况是什么？比如主串是"AAAAAAAAAB"，模式串是"AAAB"，每次都要比到最后一个字符才发现不对，然后回溯。效率低得让人抓狂。

7.3 KMP算法原理与next数组

KMP算法，全称Knuth-Morris-Pratt，三位大神联合发明。它的核心思想就一句话：利用已经匹配过的信息，让主串指针不回溯。

为什么会这样？你想想看，BF算法里每次匹配失败，i都要退回去。但如果我们已经知道模式串的前后缀关系，就可以让模式串直接跳到合适的位置，i继续往前走就行了。

这里的关键就是next数组。next[j]表示：当模式串第j个字符匹配失败时，模式串应该跳到哪个位置继续匹配。

void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

这段代码初看很绕，我当年也啃了好一阵子。其实它的逻辑是：用模式串自己匹配自己，找出每个位置的最长公共前后缀长度。next[1]=0是个约定，表示第一个字符就不匹配，那主串和模式串都得挪。

有了next数组，KMP的匹配就简单了：

int KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++; j++;
        } else {
            j = next[j];  // 模式串滑动，i不动
        }
    }
    if (j > T.length) return i - T.length;
    else return 0;
}

看到区别了吗？匹配失败时，BF是i = i - j + 2，KMP是j = next[j]。就这一行代码的差异，时间复杂度从O(n*m)降到了O(n+m)。

7.4 KMP的优化：nextval数组

KMP虽然好，但还有优化空间。你想想看，如果模式串是"AAAAAB"，next数组会怎么算？每个位置的最长公共前后缀都在递增，但匹配失败时，跳到的位置还是同一个字符，还得再比一次，又失败，再跳...这就产生了不必要的比较。

nextval数组就是解决这个问题的。它在计算next时，如果发现跳转后的字符和当前字符相同，就继续往前跳，直到跳到一个不同的字符为止。

void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++; j++;
            if (T.ch[i] != T.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        } else {
            j = nextval[j];
        }
    }
}

注意看那个if (T.ch[i] != T.ch[j])的判断。如果相等，就用nextval[j]的值，相当于递归地往前跳。这个优化在模式串有大量重复字符时效果特别明显。

7.5 知识体系总览

下面这张图是我梳理的本章知识结构，从存储到算法，再到优化，一条线串下来：

好了，模式匹配就讲到这里。记住，BF是基础，KMP是进阶，nextval是优化。从暴力到优雅，这就是算法的魅力所在。