这是你见过的最容易深刻理解的KMP算法讲解

[!NOTE]

阅读本文前请先看这篇文章：字符串匹配的KMP算法 - 阮一峰的网络日志，它讲解了KMP算法的基本思想——在笔者看来，就是利用已匹配模式串的对称性，来取消主串指针回溯带来的时间复杂度的增加，相信读者看完这篇简明易懂的文章之后，也会有这种感觉。然鹅，这篇文章实际上是不完全的KMP算法，也没有具体实现的代码，所以本文是对这篇文章的补充说明。

阮老师的这篇文章，其中移动位数 = 已匹配的字符数 - 对应的部分匹配值这个公式固然没错，也就是KMP算法的基本思想。但若按照文章里面说的那样直接“移动模式串”，就不能真正理解KMP算法的核心实现——主串指针不回溯，直接修改模式串指针。正确的操作应是把主串指针不动，而将模式串指针直接置为对应的部分匹配值（或变形），即next数组当中对应的值。（~~在这里，由于数组下标从0/1开始的不同，带来了一些差异，令人在理解上有些头疼~~）

[!TIP]

啊？为什么能将模式串指针直接置为对应的部分匹配值？别急，看推导：

从移动模式串的这种直觉看，是相对指针这把“不动的尺子”而言的吧~

但是模式串真的有在移动吗？没有吧！所以向右移动字符串，实际上是不是指针在向左移，相当于在给指针做减法呢？~~话说，这有点像物理里面的参考系吧~~

所以模式串指针置为的值，就应该是已匹配的字符数 - 移动位数，等于已匹配的字符数 - （已匹配的字符数 - 对应的部分匹配值），那么也就是对应的部分匹配值了~

在这里得提一嘴前缀函数与next数组的关系：next数组就是前缀函数的变形。前缀函数在某位元素对应的值，是它的前缀与后缀最长相等的长度；而next数组因为在该位元素处已经失配，所以应该对应它前一位的前缀函数值。1序数组则是在0序数组的基础上值均增加了1，如下图所示。所以说，next数组并非很高深的东西。

这里需要注意的就是模式串的第一个字符就与主串的某个字符匹配不上的情况（即模式串第一位就失配），对应0序next数组取到-1时，或1序next数组取到0时。如果是这样，那么需要把主串的指针也往后移一位。如阮老师文章中11.这种情况。

好的，KMP算法的思想这里已经大体讲完了。如果想要快速解题，比如直接让你求next/nextval数组，我的建议是学一下秒杀技巧，在这里推荐这个up主的视频：https://www.bilibili.com/video/BV1PKXPBnEf9

[!NOTE]

本文代码均基于0序next数组实现。

但是但是，这个next数组是我们人眼看出来的啊？代码又应该怎么写呢？这就是最难理解的部分了（~~个人感觉~~）。不过，我发现了一个很好的讲解视频，在这里给出链接：https://www.bilibili.com/video/BV16X4y137qw

我复述一遍这个视频中求next数组的关键思想，参考图如下：

整条黄色的就是已经求好next数组的模式串。next数组对应的下一个值，就是要考察第二个绿色后面的值是否等于第一个绿色后面的值。若ch[i] == ch[j]两者相等，则next[++i] = ++j;若不相等，执行j = next[j]，j跳转指向第一个蓝色后面。由绿色中的蓝色部分也相等可知，这四个蓝色也相等，所以再考察最后一个（第四个）蓝色后面的值是否等于第一个蓝色后面的值。然后再进行如上循环，如果直到j == -1仍未结束，说明该新值ch[i]与首值ch[j]都不相等，触发了特判条件，将该值对应的next值置为0。这样，我们就完成了next数组的求解。

GetNext函数实现：

void GetNext(const string& ch, vector<int>& next)
{
    int length = ch.length();
    next[0] = -1;
    int i = 0, j = -1;
    while(i < length){
        if(j == -1 || ch[i] == ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}

至于kmpSearch这个函数，就是前面所说的kmp的核心实现。特别注意，当模式串第一位就失配时，此时j = 0，对应的next[j] = -1，触发了特判条件，从而实现主串的指针也往后移一位的功能。

bool kmpSearch(const string& S, const string& P) {
    int n = S.length();
    int m = P.length();

    vector<int> next(m + 1);
    GetNext(P, next);

    int i = 0, j = 0;
    while(i < n){
        if(j == -1 || S[i] == P[j]) {
            i++;
            j++;
        }
        else j = next[j];
        if (j == m) return true;
    }
    return false;
}