字符串与KMP算法：从朴素匹配到高效查找

字符串匹配，说白了就是在一个长字符串里找一段短字符串。这活儿我们天天干——编辑器里的查找功能、搜索引擎的关键词匹配、甚至你手机通讯录的搜索，背后都是这套逻辑。

我个人习惯把字符串匹配分成两类：一类是“暴力找”，一类是“聪明找”。今天我们就从暴力开始，一步步走到KMP这个经典算法。

字符串的存储结构

在C语言里，字符串其实就是一个字符数组，以'\0'结尾。这个设计有好有坏——好处是简单，坏处是你得时刻记着那个结尾符。

// 常见的字符串存储方式
char str1[] = "hello";          // 自动加'\0'，长度6
char str2[] = {'h','e','l','l','o','\0'}; // 手动加，效果一样
char *str3 = "hello";           // 字符串常量，不可修改

对于模式匹配来说，我们通常用两种方式表示字符串长度：

• 显式长度：用一个int变量存长度，比如int len = 5;
• 隐式长度：靠'\0'判断结尾，每次遍历都检查

我个人更推荐显式长度，尤其在算法实现里——少一次判断，少一个坑。

朴素模式匹配：暴力但直观

朴素匹配的思路很简单：从主串的第一个字符开始，跟模式串逐个比较。如果匹配失败，主串指针回溯到下一个位置，模式串指针回到开头，重新来。

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

这个算法的时间复杂度是O(n*m)。最坏情况什么样？你想想看——主串是"AAAAAA...AAB"，模式串是"AAAB"，每次都要比到最后一个字符才发现不对，然后回溯。我遇到过这种数据，跑起来慢得让人抓狂。

KMP算法原理：不回溯的智慧

KMP算法的精髓就一句话：主串指针永不回溯，模式串指针根据已知信息跳着走。

为什么会这样？因为当匹配到某个位置失败时，我们已经知道前面那些字符是什么了。利用这个信息，我们可以让模式串跳过一些肯定匹配不上的位置。

举个例子：主串"ababcabcabababd"，模式串"ababd"。当匹配到第5个字符时，'c'和'd'不匹配。但前面"abab"我们已经比对过了，其中"ab"这个前缀在模式串里重复出现过。所以模式串可以直接跳到第三个字符开始比，主串不用动。

next数组：KMP的核心

next数组记录了模式串每个位置之前的子串中，最长相等前后缀的长度。说白了就是：如果在这个位置匹配失败，模式串应该跳到哪个位置继续比。

我们来看怎么计算next数组：

void get_next(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];  // 回溯
        }
    }
}

这里有个细节：next[0] = -1。为什么是-1？因为第一个字符就匹配失败时，模式串已经没有可以回退的位置了，只能让主串前进一位。用-1作为一个特殊标记。

有了next数组，KMP的匹配过程就清晰了：

int kmp_match(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int next[m];
    get_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 - m;
    }
    return -1;
}

你看，主串的指针i只增不减，这就是KMP高效的原因——时间复杂度O(n+m)。

知识体系总览

下面这张图把整个流程串起来了，建议你对照着看：

next数组的优化：改进版

标准的next数组有个小问题。你想想看，如果pattern[i] == pattern[next[i]]，那跳过去之后还是比不上的，白跳了。所以有了改进版：

void get_next_improved(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++;
            // 改进点：如果相等，继续递归
            if (pattern[i] != pattern[j]) {
                next[i] = j;
            } else {
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

这个优化在实际项目中很有用。我记得有一次处理超长文本搜索，用改进版比标准版快了将近20%。虽然看起来只是多了一个判断，但减少了很多无效跳转。

好了，字符串匹配这块儿就聊到这儿。KMP不是唯一的高效匹配算法，但它是理解更高级算法（比如BM、Sunday）的基础。把next数组搞明白，后面学什么都快。

---