KMP入门级别算法详解--终于解决了（next数组详解）

Dear 丶 2022-06-10 10:25 171阅读 0赞

对于正常的字符串模式匹配，主串长度为m，子串为n，时间复杂度会到达O（m\*n），而如果用KMP算法，复杂度将会减少线型时间O（m+n）。

设主串为ptr="ababaaababaa";，要比较的子串为a=“aab”；

KMP算法用到了next数组，然后利用next数组的值来提高匹配速度，我首先讲一下next数组怎么求，之后再讲匹配方式。

next数组详解

首先是理解KMP算法的第一个难关是next数组每个值的确定，这个问题困恼我很长时间，尤其是对照着代码一行一行分析，很容易把自己绕进去。

定义一串字符串

ptr = "ababaaababaa";

## next\[i\]（i从1开始算）代表着，除去第i个数，在一个字符串里面从第一个数到第（i-1）字符串前缀与后缀最长重复的长度。（这里看不懂继续往下看就行） ##

什么是前缀？

在“aba”中，前缀就是“ab”，除去最后一个字符的剩余字符串。

同理可以理解后缀。除去第一个字符的后面全部的字符串。

在“aba”中，前缀是“ab”，后缀是“ba”，那么两者最长的子串就是“a”；

在“ababa”中，前缀是“abab”，后缀是“baba”，二者最长重复子串是“aba”；

在“abcabcdabc”中，前缀是“abcabcdab”，后缀是“bcabcdabc”，二者最长重复的子串是“abc”；

### 这里有一点要注意，前缀必须要从头开始算，后缀要从最后一个数开始算，中间截一段相同字符串是不行的。 ###

在next数组中，有两种定义方式：（定义方式可以先不用管，继续往下看，看懂了再回来看）

第一种是next\[1\]=-1,next\[2\]=-1。这里的-1代表没有匹配，1代表匹配了1位。

第二种是规定next\[1\]=0,next\[2\]=1。（第二种方法之后会讲）这里0与1是规定，后面的匹配中，如果1位匹配，则规定next值为2（就是匹配的位数+1）。

先看第一种规定方法：

再回到next\[i\]的定义，对于字符串ptr = "ababaaababaa";

next\[1\] = -1，字符串“a”，要进行next数组运算，也就是代表着除了第一个元素，它本身之前的 前缀 与 后缀 最长的重复子串，这里是空 ,即""，没有，我们记为-1，代表空。（0代表1位相同，1代表两位相同，依次累加）。

next\[2\] = -1，字符串为“ab”，要进行计算的字符串为“a”（要扣除当前字符“b”，所以只剩下“a”），没有前缀与后缀，故最长重复的子串是空，值为-1；

next\[3\] = -1，字符串为“aba”，要进行计算的字符串为“ab”（要扣除当前字符“a”，所以只剩下“ab”），前缀是“a”，后缀是“b”，最长重复的子串“”；

next\[4\] = 1，字符串为“abab”，要进行计算的字符串为"aba"（要扣除当前字符“b”，所以只剩下“aba”），前缀是“ab”，后缀是“ba”，最长重复的子串“a”；next数组里面就是最长重复子串字符串的长度

next\[5\] = 2，字符串为“ababa”，要进行计算的字符串为"abab"（要扣除当前字符“a”，所以只剩下“abab”），前缀是“aba”，后缀是“bab”，最长重复的子串“ab”；

next\[6\] = 3，字符串为“ababaa”，要进行计算的字符串为"ababa"（要扣除当前字符“a”，所以只剩下“ababa”），前缀是“abab”，后缀是“baba”，最长重复的子串“aba”；

next\[7\] = 1，字符串为“ababaaa”，要进行计算的字符串为"ababaa"（要扣除当前字符“a”，所以只剩下“ababaa”），前缀是“ababa”，后缀是“babaa”，最长重复的子串“a”；

next\[8\] = 1，字符串为“ababaaab”，要进行计算的字符串为"ababaaa"（要扣除当前字符“b”，所以只剩下“ababaaa”），前缀是“ababaa”，后缀是“babaaa”，最长重复的子串“a”；

next\[9\] = 2，字符串为“ababaaaba”，要进行计算的字符串为"ababaaab"（要扣除当前字符“a”，所以只剩下“ababaaab”），前缀是“ababaaa”，后缀是“babaaab”，最长重复的子串“ab”；

next\[10\] = 3，字符串为“ababaaabab”，要进行计算的字符串为"ababaaaba"（要扣除当前字符“b”，所以只剩下“ababaaaba”），前缀是“ababaaab”，后缀是“babaaaba”，最长重复的子串“aba”；

next\[11\] = 4，字符串为“ababaaababa”，要进行计算的字符串为"ababaaabab"（要扣除当前字符“a”，所以只剩下“ababaaabab”），前缀是“ababaaaba”，后缀是“babaaabab”，最长重复的子串“abab”；

next\[12\] = 5，字符串为“ababaaababaa”，要进行计算的字符串为"ababaaababa"（要扣除当前字符“a”，所以只剩下“ababaaababa”），前缀是“ababaaabab”，后缀是“babaaaababa”，最长重复的子串“ababa”；

所以字符串ptr = "ababaaababaa"的next数组为：-1，-1，-1,1,2,3,1,1,2,3,4,5

# 第二种方法中： #

变化的只有下标，原理都一样。

这里我们定义next\[1\] = 0 , next\[1\] = 1;

再分析ptr字符串，ptr = "ababaaababaa";

跟上一个的情况类似，

next\[1\] = 0 ,事先定义好的

next\[2\] = 1 ,事先定义好的

next\[3\] = 1 ,最长重复的子串“”；1代表没有重复，2代表有一个字符重复。

next\[4\] = 2 ，最长重复的子串“a”；追偿的长度加1，即为2.

next\[5\] = 3 ，以下都跟之前的一样，这种方法是最长的长度再加上一就可以了。

next\[6\] = 4

next\[7\] = 2

next\[8\] = 2

next\[9\] = 3

next\[10\] = 4

next\[11\] = 5

next\[12\] = 6

以上是next数组的详细解释。next数组求值 是比较麻烦的，剩下的匹配方式就很简单了。

next数组用于子串身上，根据上面的原理，我们能够推出子串a=“aab”的next数组的值分别为0,1,2.（按照我说的第二种方式算的）。

首先开始计算主串与子串的字符，设置主串用i来表示，子串用j来表示，如果ptr\[i\]与a\[i\]相等，那么i与j就都加1：

![Center][]

prt\[1\]与a\[1\]相等，i++，j++：

用代码实现就是

if( j==0 ||  ptr[i]==a[j])
    {
        ++i;
        ++j;
    }

![Center 1][]

ptr\[2\]与a\[2\]不相等

此时ptr\[2\]!=a\[2\]，那么令j = next\[j\]，此时j=2，那么next\[j\] = next\[2\] = 1.那么此时j就等于1.这一段判断用代码解释的话就是：

if( ptr[i]!=a[j])
    {
          j = next[j];
    }

加上上面的代码进行组合：

在对两个数组进行比对时，各自的i，j取值代码：

while( i<ptr.length && j< a.length)
    {
         if( j==0 || ptr[i]==a[i] )
        {
              ++i;
              ++j;

next[i] = j;
        }
        else
        {
              j = next[j];
        }
    }

此时将a\[j\]置于j此时所处的位置，即a\[1\]放到j=2处，因为在j=2时出现不匹配的情况。

![Center 2][]

此时再次计算是否匹配，可以看出来a\[1\]!=ptr\[2\],那么j = next\[j\]，即此时j = next\[1\] = 0;

根据上面的代码，当j=0时，执行++i；++j；

此时就变为：

![Center 3][]

此时ptr\[3\] = a\[1\],继续向下走，下一个又不相等了，然后“aab”向后挪一位，这里不再赘述了，主要的思想已经讲明白了。到最后一直到i = 8，j=3时匹配成功，KMP算法结束。整个过程就结束了。

[Center]: /images/20220610/807fd581680244d6a17f4974a9261abf.png
[Center 1]: /images/20220610/f59785ff690d4171bcc40008e49f5707.png
[Center 2]: /images/20220610/61957102d307466f8db73d6dc1e7d01e.png
[Center 3]: /images/20220610/ade0243fe0044d14a17096864fdd0d02.png