[KMP算法]最简单通俗易懂求next数组的方法

什么是KMP算法

KMP算法又称看毛片算法，是用来进行字符匹配的，比如要检查一个字符串S[]里是否有字符串P[]，如果用暴力算法的话，也是可以解的，但是效率特别低，时间复杂度为O（m*n），而如果你用看毛片算法的话，时间复杂度为O（m+n）。
本文先单独讲述kmp算法中一个重要的数组——next[]数组的求法，如果一个字符没有匹配成功，那么进行查询next数组将指针回溯，也可以理解成将目标数组往后移。

next数组的求法

首先，我们要先懂得怎样求最长前缀表，比如
abcab 的最长前缀是 2
abcd 的最长前缀是 0
abcabc 的最长前缀是 3

接下来告诉大家怎么求next数组
以下图这个数组为例，下标从0开始，首先先把前缀表的第一位赋值为0。

然后将P写成如下的形式，即将P[0]-P[n] (nshuyu 1-8)写出，分别计算最长前缀。

然后将结果填入，就

敲重点！！
上图所示这个并不是我们要的next数组，而是个前缀表prefix，但是我们离next数组已经很近了！
我们将prefix数组的最后一个值，即prefix[8]去掉，将prefix[0]前面加一个 -1 再整体左移一位，就可以得到next数组了。看图！

代码实现

（文末有福利）

// An highlighted block
#include<bits/stdc++.h>
using namespace std;
void prefix_table(char p[],int prefix[],int l)
{
    prefix[0] = 0;
    int i = 1;
    int len = 0;
    while(p[i]!=0){
        if(p[len]==p[i]){
            len++;
            prefix[i]=len;
            i++;
        }
        else{
            if(len>0){
                len=prefix[len-1];
            }
            else {
                prefix[i]=len;
                i++;
            }
        }

    }
}

int main()
{
    int n=9;
    char p[]={"ABABCABAA"};
    int prefix[9];
    prefix_table(p,prefix,n);
    for(int i=0;i<n;i++){
        cout<<prefix[i]<<endl;
    }
    return 0;
}

看不懂，没关系，给你们个福利，b站 av16828557 看完你会恍然大悟的
我就是从那位老哥那听懂的kmp，图片也是从他视频里截取的。
喜欢的记得给我点个关注~