03、KMP

KMP 算法（Knuth-Morris-Pratt）

我们刚才讲了 BM 算法，虽然不是特别容易理解，但是如果你用心看的话肯定可以看懂的，我们再来看一个新的算法，这个算法是考研时必考的算法。实际上 BM 和 KMP 算法的本质是一样的，你理解了 BM 再来理解 KMP 那就是分分钟的事啦。

我们先来看一个实例

为了让读者更容易理解，我们将指针移动改成了模式串移动，两者相对与主串的移动是一致的，重新比较时都是从指针位置继续比较。

通过上面的实例是不是很快就能理解 KMP 算法的思想了，但是 KMP 的难点不是在这里，不过多思考，认真看理解起来也是很轻松的。

在上面的例子中我们提到了一个名词，最长公共前后缀，这个是什么意思呢？下面我们通过一个较简单的例子进行描述。

最长公共前后缀

KMP例子

此时我们在红色阴影处匹配失败，绿色为匹配成功部分，则我们观察匹配成功的部分。

我们来看一下匹配成功部分的所有前缀

我们的最长公共前后缀如下图，则我们需要这样移动

原理

好啦，看完上面的图，KMP 的核心原理已经基本搞定了，但是我们现在的问题是，我们应该怎么才能知道他的最长公共前后缀的长度是多少呢？怎么知道移动多少位呢？

刚才我们在 BM 中说到，我们移动位数跟主串无关，只跟模式串有关，跟我们的 bc,suffix,prefix 数组的值有关，我们通过这些数组就可以知道我们每次移动多少位啦，其实 KMP 也有一个数组，这个数组叫做 next 数组，那么这个 next 数组存的是什么呢？

next数组

什么是 next 数组

next 数组存的咱们最长公共前后缀中，前缀的结尾字符下标。是不是感觉有点别扭，我们通过一个例子进行说明。

next数组

next数组的作用

我们知道 next 数组之后，我们的 KMP 算法实现起来就很容易啦，另外我们看一下 next 数组到底是干什么用的。

KMP1

image-20251102220559470

剩下的就不用说啦，完全一致啦，咱们将上面这个例子，翻译成和咱们开头对应的动画大家看一下。

请添加图片描述

下面我们看一下代码，标有详细注释，大家认真看呀。

注：很多教科书的 next 数组表示方式不一致，理解即可

代码

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 处理特殊情况
        if (needle.empty()) {
            return 0;
        }
        if (haystack.empty()) {
            return -1;
        }
        
        // 转换为字符数组
        const char* hayarr = haystack.c_str();
        const char* nearr = needle.c_str();
        
        // 获取长度
        int halen = haystack.length();
        int nelen = needle.length();
        
        // 调用KMP算法
        return kmp(hayarr, halen, nearr, nelen);
    }
    
private:
    int kmp(const char* hayarr, int halen, const char* nearr, int nelen) {
        // 获取next数组
        vector<int> next = getNext(nearr, nelen);
        int j = 0;
        
        for (int i = 0; i < halen; ++i) {
            // 不匹配时，根据next数组移动指针
            while (j > 0 && hayarr[i] != nearr[j]) {
                j = next[j - 1] + 1;
                // 超出长度时，直接返回不存在
                if (nelen - j + i > halen) {
                    return -1;
                }
            }
            
            // 字符匹配，指针同时后移
            if (hayarr[i] == nearr[j]) {
                ++j;
            }
            
            // 匹配完成，返回起始位置
            if (j == nelen) {
                return i - nelen + 1;
            }
        }
        
        // 未找到匹配
        return -1;
    }
    
    // 计算next数组
    vector<int> getNext(const char* needle, int len) {
        vector<int> next(len);
        next[0] = -1;
        int k = -1;
        
        for (int i = 1; i < len; ++i) {
            // 回溯寻找最长公共前后缀
            while (k != -1 && needle[k + 1] != needle[i]) {
                k = next[k];
            }
            
            // 找到匹配的字符，更新最长公共前后缀长度
            if (needle[k + 1] == needle[i]) {
                ++k;
            }
            
            next[i] = k;
        }
        
        return next;
    }
};