容易理解的KMP算法next数组求法详解

程序员文章站 2022-03-31 21:17:42

...

如果你知道KMP算法的思想但还是自己写不出来，我猜你大概是不太明白next数组的求法。
网上很多关于KMP算法的博客写的都及其抽象和模棱两可。
我的上一篇博客小白也能看懂的KMP算法就是结合网上讲解的较为详细的博客，和学校老师的讲解，用自己的理解整合写出的。在里面开篇我就用大白话把KM这种算法令人砰然心动的地方讲解出来。
对于学什么东西，知道它好在哪，它的灵感来自于哪，适用于什么场景，很重要。就像有很多人刚开始学反射的时候，代码和原理是学了，但是就比如好好的修改属性，为啥要用反射而不是直接修改呢？这就是对于上面那三个问题没有想明白而造成的。
废话不多说，上一篇小白也能看懂的 KMP算法重点是思想的讲解和上面的三个问题(它好在哪，它的灵感来自于哪，适用于什么场景) 的解答。
这篇是关于KMP算法里面的重中之重 next数组的求法的解答。
正文开始：
注意：由于有的语言喜欢在字符串第一位存长度所以个别语言中字符串内容是从下标1开始的
用内容从下标1开始的字符串来举例的好处就是下标和顺序一一对应下标1就是第一个
当然，即使不是用第一位存储长度的语言，也可故意舍弃第一位不用从下标1开始这样好对应也方便理解

第一个的是偏数学的理论证明，如果看不明白，直接看第二个更为白话的next原理解读。

假设KMP算法中的模式串为P，主串为S，那么该算法中的核心是计算出模式串的P的next函数。

KMP算法是在已知的模式串的next函数值的基础上进行匹配的。

由于本次只讨论next的求值过程，因此KMP算法的数学推理过程这里不再讲解。

从KMP算法的数学推理可知，此next函数只取决与模式匹配串自身的特点和主串没有任何关系，此函数

默认认为next[1]=0，由于next[j]=k表示的意义是当模式串和主串的第j个字符不匹配时，那么接下来和主串的第j个

字符匹配的字符是模式串的第k个字符。因此，next[1]=0表示当主串的当前字符和模式串的第1个字符不匹配，接

下来需要用模式串的第0个字符和主串的当前字符匹配，由于模式串下标是从1开始的，所以不可能存在第0个字符，

即接下的匹配动作是主串和模式串同时向右移动一位，继续模式匹配。
容易理解的KMP算法next数组求法详解此时，主串和模式串不匹配，而next[1]=0，因此，模式串的第0个字符和主串的第2个字符比较，而模式串没有第0个

字符，此时可以把第0个字符理解为空字符，即模式串向右移动一位，主串再继续喝模式串匹配，而此时的主串的当

前字符是第3个字符，整体来看是当主串和模式串的第1个字符不匹配时，主串和模式串同时右移一位，然后继续匹配。

接下来讲解一般情况下的next函数值求解过程。

设next[j]=k，根据KMP算法的模式串的特点可知，‘p1p2…pk-1’=‘pj-k+1…pj-1’，其中k必须满足1<k<j，并且不可能存在k‘>k满足上面等式。那么能够根据next[j]=k计算出next[j+1]的值吗？显然是能够计算出来的。
下面讨论具体求解过程：

当知道next[j]=k的值，求next[j+1]的值时候有两种情况，一种是pk=pj，另一种情况是pk!=pj。

1.当pk=pj时，那么可以得出在模式串中存在‘p1…pk’=‘pj-k+1…pj’子串等式。并且不可能存在k‘>k，满足

"p1…pk’ “=” pj-k’+1…pj "等式（该等式中用的是双引号，只是为了区别外边字符串的引号和内部k‘的引号，没有其它意图，特此说明），因为根据KMP算法的说明k是最大的。

因此，显而易见next[j+1]=k+1=next[j]+1。该式表示当主串的当前字符和模式串的第j+1个字符不匹配时，需要使用模式串的第k+1个字符和当前主串字符比较匹配，即主串的当前字符不变，变的只是模式串的字符，可以理解为模式串向右移动j+1-（k+1）=j-k个字符。
2.当pk!=pj时，可知在模式串中不存在‘p1…pk’=‘pj-k+1…pj’等式。表明不能简单的用模式串的第k+1个字符和主串比较，因为pk!=pj，此时需要把模式串向右移动更多的位数，直到找出模式串的前m个字符和主串中的m个字符匹配为止或者没有找到这样的子串，那么意味着模式串需要从第1个字符开始和主串从新匹配。
容易理解的KMP算法next数组求法详解因为已经知道next[j]=k，因此可知模式串中p1=pj-k+1，p2=pj-k+2，…，pk-1=pj-1，则此时应该将模式串继续向右移动直到第m+1个字符，该字符满足’p1…pm‘=’pj-m+1…pj‘，（1<m<k<j）并且不存在m’>m也满足该等式。此时就可以使用第m+1个字符和当前主串字符比较匹配，（假设当前主串的字符索引是i+1）

此时主串中必存在关系式‘si-m+1…si’=‘pj-m+1…pj’=‘p1…pm’，因此用模式串的第m+1个字符和当前主串字符比较匹配是正确的。此时next[j+1]=m+1=next[…next[next[k]]]+1。

这里m=next[…next[next[k]]]，这里解释一下m=next[…next[next[k]]]，由于pk!=pj，因此需要向右移动模式串，

首先移动第next[k]个字符和第j个字符比较，假设next[k]=h，如果ph=pj，

则说明模式串中存在等式‘p1…ph’=‘p-h+1…pj’，（1<h<k<j）（假设主串中当前和模式串比较字符是第i+1个）则主串中必然存在‘si-h+1…si’=‘pj-h+1…pj’=‘p1…ph’等式（1<h<k<j）。也就是说next[j+1]=h+1。

                                                      即next[j+1]=next[k]+1。

同理，如果ph!=pj，则模式串还需要继续向右移动，用第next[h]个字符和第j个字符比较，以此类推，直到第j个字符和模式串中的某个字符匹配成功或者不存在u（1<u<j）满足等式‘p1…pu’=‘pj-u+1…pj’。如果找到了匹配字符u，那么

next[j+1]=u+1，否则next[j+1]=1。
如果上面的推导过程对你来说过于晦涩，请换成看下面的
——————————————————————————————————————————————
动图失效了，参考博客是https://blog.csdn.net/qq_37969433/article/details/82947411，直接去看吧
容易理解的KMP算法next数组求法详解

手动写出一个串的next值

我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
容易理解的KMP算法next数组求法详解这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子：
容易理解的KMP算法next数组求法详解

求next的算法

短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释

int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch[i]==ch[j])
        	 next[++i] = ++j;
        else j = next[j];
    }
}

还是先由一般再推优化：
①直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的首尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
这句话太重要了，放大再看一遍

每次前去尾1个，后掐头1个，直至得到next[j+1]

②再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：

1、next[j+1]的最大值为next[j]+1。
因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

开——始——划——重——点！

从头走一遍流程
①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推