第12章字符串匹配算法

课程目录第12章字符串匹配算法

12. 字符串匹配算法：朴素匹配与 KMP 的原理与 C 语言实现

字符串匹配，说白了就是在一段长文本里找一段短字符串。比如你在记事本里按 Ctrl+F 搜一个词，背后就是匹配算法在工作。

我刚开始学的时候，觉得这有什么难的？一个循环挨个比不就完了？后来真到项目里才发现——当文本有几百万字符，模式串又很长的时候，那个「挨个比」慢得让人抓狂。嗯，这时候就得请出 KMP 了。

12.1 朴素匹配算法

朴素匹配的思路非常直白：从文本的第一个字符开始，跟模式串的第一个字符比。如果一样，就继续比下一个；如果不一样，就把模式串整体往后挪一位，再从模式串开头重新比。

你想想看，这就像拿着一把尺子在文本上滑动，每滑一次就比一轮。代码写起来也很简单：

#include <stdio.h>
#include <string.h>

int naive_match(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int i, j;

    for (i = 0; i <= n - m; i++) {
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j])
                break;
        }
        if (j == m)
            return i;  // 匹配成功，返回起始位置
    }
    return -1;  // 没找到
}

这个算法的时间复杂度是 O(n*m)。最坏情况什么样？我举个例子：文本是 "AAAAAAAAAAAAAB"，模式串是 "AAAB"。每次都比到最后一个字符才发现不对，然后挪一位重新比。这种场景下，效率确实低。

注意：朴素匹配在大多数「正常」文本中表现还行。但如果你处理的是重复字符很多的字符串（比如基因序列、日志文件），它的性能会急剧下降。我曾经在一个日志分析工具里用过朴素匹配，结果处理 10MB 的文件花了十几秒——后来换成 KMP，一秒不到就搞定了。

12.2 KMP 算法的核心思想

KMP 的全称是 Knuth-Morris-Pratt，三个大佬的名字。它的核心思想就一句话：利用已经匹配过的信息，不要让模式串每次都从头开始比。

为什么会这样？你想想看，在朴素匹配里，如果我们在第 5 个字符上匹配失败了，模式串就整体往后挪一位，然后从模式串的第 0 位重新比。但有时候，模式串的前缀和后缀有重复的部分，这些重复信息是可以复用的。

KMP 的做法是：提前算好一个 next 数组（也叫部分匹配表），记录当某个位置匹配失败时，模式串应该跳到哪个位置继续比。这样文本指针永远不会回溯，只有模式串的指针在跳。

  一句话总结：KMP 让文本指针只往前走，不走回头路。匹配失败时，模式串根据 next 数组「聪明地」往后跳，而不是傻傻地只挪一位。

12.3 构建 next 数组

next 数组的每个值表示：模式串中，当前位置之前的子串里，最长的相等前后缀的长度。

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

位置 i	0	1	2	3	4	5
字符	A	B	A	B	A	C
next[i]	-1	0	0	1	2	3

怎么算的？我习惯用「自己跟自己比」的方法：

i=0：next[0] 固定为 -1，表示第一个字符就不匹配，直接挪文本指针
i=1：子串 "A"，没有前后缀，next=0
i=2：子串 "AB"，前缀 "A" ≠ 后缀 "B"，next=0
i=3：子串 "ABA"，前缀 "A" = 后缀 "A"，长度为 1，next=1
i=4：子串 "ABAB"，前缀 "AB" = 后缀 "AB"，长度为 2，next=2
i=5：子串 "ABABA"，前缀 "ABA" = 后缀 "ABA"，长度为 3，next=3

代码实现如下：

void build_next(const char *pattern, int *next) {
    int m = strlen(pattern);
    next[0] = -1;
    int i = 0, j = -1;

    while (i < m - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

这段代码我第一次看的时候也觉得绕。其实核心就是：用两个指针 i 和 j，i 往前走，j 往回跳。如果字符相等，两个指针一起走；如果不相等，j 就根据已有的 next 值往回跳。

12.4 KMP 匹配过程

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

int kmp_match(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int next[m];
    build_next(pattern, next);

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }

    if (j == m)
        return i - j;
    return -1;
}

注意看，文本指针 i 只增不减。这就是 KMP 高效的原因——它不会像朴素匹配那样，匹配失败后把 i 往回退。

我的经验：KMP 的 next 数组构建是容易出错的地方。我建议你写完之后，拿几个小例子手动跑一遍，确认 next 值对不对。比如 "AAAA" 的 next 数组应该是 [-1, 0, 1, 2, 3]，很多人会算成 [-1, 0, 1, 2, 2]，区别就在最后一个位置。

12.5 朴素匹配 vs KMP：对比总结

对比项	朴素匹配	KMP
时间复杂度	O(n*m)	O(n+m)
空间复杂度	O(1)	O(m)
文本指针回溯	会回溯	不回溯
实现难度	简单	中等
适用场景	短文本、随机字符	长文本、重复字符多

我个人习惯是：如果模式串长度小于 10，或者文本很短，直接用朴素匹配就够了。代码简单，不容易出错。但如果要处理大文件或者性能敏感的模块，我会毫不犹豫上 KMP。

12.6 核心逻辑流程图

下面这张图展示了朴素匹配和 KMP 在匹配失败时的不同处理方式：

从图上可以看得很清楚：朴素匹配失败后，文本指针要往回退，模式串从头开始；而 KMP 的文本指针不动，模式串根据 next 数组跳到合适的位置继续比。这就是 KMP 快的原因。

12.7 避坑指南

我曾经在一个嵌入式项目里用 KMP，结果发现 next 数组算错了，导致匹配结果时对时错。排查了半天才发现是 next 数组的边界条件没处理好。这里分享几个容易踩的坑：

next[0] 必须初始化为 -1：这是为了在第一个字符就不匹配时，能正确让文本指针前进
模式串长度为 0 或 1 时：需要特殊处理，否则 next 数组构建会越界
next 数组的索引和模式串的索引要对应好：next[i] 表示的是 pattern[0..i-1] 这个子串的信息，不是 pattern[0..i]

重要提醒：KMP 的 next 数组有多种定义方式。有的教材把 next[0] 定义为 0，有的定义为 -1。我个人习惯用 -1 版本，因为这样在匹配代码里逻辑更统一。不管你用哪种，一定要前后一致，别混着用。

好了，字符串匹配这块就讲到这里。朴素匹配简单直接，适合快速实现；KMP 稍微复杂一点，但性能优势明显。我建议你把两种都写一遍，跑几个测试用例对比一下，感受会更深刻。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

12. 字符串匹配算法：朴素匹配与 KMP 的原理与 C 语言实现

12.1 朴素匹配算法

12.2 KMP 算法的核心思想

12.3 构建 next 数组

12.4 KMP 匹配过程

12.5 朴素匹配 vs KMP：对比总结

12.6 核心逻辑流程图

12.7 避坑指南