最通俗易懂的求next数组的方法（KMP算法）

客官°小女子只卖身不卖艺 2022-10-15 10:48 183阅读 0赞

# 一、[字符串匹配的KMP算法][KMP] #

相信小伙伴们看了阮一峰老师讲解的KMP算法后也会有醍醐灌顶的感觉。可惜，阮老师没有去讲如何求部分匹配表（Partial Match Table），但这也是写出KMP算法的关键所在。所以，我打算再详细讲讲如何求部分匹配表，也即next数组。

# 二、求部分匹配表（next数组） #

![在这里插入图片描述][2021052419071661.png]

## 1.部分匹配值 ##

①前缀  
1个字符串除去末尾字符，以首字符开头的所有子串。  
②后缀  
1个字符串除去首字符，以末尾字符结尾的所有子串。

> 比如：字符串：ABCDAB  
> 前缀：A、AB、ABC、ABCD、ABCDA  
> 后缀：BCDAB、CDAB、DAB、AB、B

③部分匹配值  
前缀和后缀的最长公共子串长度

> 对于ABCDAB，其部分匹配值为2，即最长公共子串AB的长度为2。

## 2.求解过程 ##

(0)由于部分匹配值和前缀和后缀有关，所以有如下定义：  
①`变量i`指向**后缀**的末尾；  
②`变量j`指向**前缀**的末尾；  
③next数组。

(1)初始化  
①由于模式串"ABCDABD"的首字符’A’前后缀都为0，所以next\[0\] = 0;（即求好了"A"的部分匹配值）  
②接下来求"AB"的部分匹配值，前缀为"A"，后缀为"B",按照上文对`i`和`j`的定义，此时`j = 0`, `i = 1`;

此时，代码框架如下：

char[] pattern = "ABCDABD";
    int[] next = new int[pattern.length];
    next[0] = 0;
    int j = 0;
    for(int i = 1; i < pattern.length; i++) {
        
    	......
    }

![在这里插入图片描述][20210524192756560.png]

(2)2种情况  
1） `pattern[j] != pattern[i]`  
这部分是难点，我猜很多小伙伴对这部分不理解的地方是①为啥要回退`j`以及②怎么回退。  
先解释①：

> 比如，“ACBDA”，当j = 1, i = 4时，虽然’C’ != ‘A’，但"ACBDA"的部分匹配值为1。所以，当`pattern[j] != pattern[i]`时，需要回退j！而之所以会产生这种情况，归根结底因为`变量j`指向**前缀**的末尾。

再解释②：  
阮一峰老师提到，移动位数 = 已匹配的字符数 - 对应的部分匹配值。  
![在这里插入图片描述][20210524222553862.png]

> 以上图为例，红框处，'D’的下标为p = 6, 空格的下标为q。此时不匹配需要回退p。p - 移动位数 = p - (p - 2) = 2（即"ABCDABD"的’C’处，而2恰好就是next\[p - 1\]！后文解释，已匹配的字符数显然是p）也就是说，`p回退到next[p - 1]`!

通过这个例子，我们得出了重要结论：

*  只要不匹配（`while(pattern[p] != pattern[q])`），`p = next[p - 1];` 当然，为了保证next\[p - 1\]不越界，更合理的写法是：

while(p > 0 && pattern[p] != pattern[q])
    	p = next[p - 1];

*  p决定了已匹配的字符数。

有没有突然觉得`pattern[j] != pattern[i]`也是一样的道理呢！同样是因为没有匹配上所以要回退。可见，j和p的逻辑是一样的，因此，回退j的方法：

while(j > 0 && pattern[j] != pattern[i])
    	j = next[j - 1];

2）`pattern[j] == pattern[i]`  
按照上文的讲述，此时next数组的情况如下：  
![在这里插入图片描述][20210524223830986.png]  
接下来，就遇到了`pattern[j] == pattern[i]`，既然前缀末尾和后缀末尾匹配上了，`j++`，指向下1个待判断的字符，而由上文可知，j和p的逻辑是一样的，均决定了已匹配的字符数，所以，`next[i] = j`;

if(pattern[j]==pattern[i]) {
        
    	j++;
    	next[i] = j;
    }

![在这里插入图片描述][20210524225314296.png]

> 上文提到：p = 6时，没有匹配，p = next\[p - 1\] = next\[5\] = 2。（说好的后文解释，没有鸽:)）

(3)构建next数组的代码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]

# 三、秒杀力扣题：[28. 实现 strStr()][28. _ strStr] #

*  AC代码

class Solution {
        
        public int strStr(String haystack, String needle) {
        
            return KMP(haystack, needle);
        }
        private int KMP(String text, String pattern) {
        
            int lenP = pattern.length();
            if(lenP == 0) return 0;
            int[] next = new int [lenP];
            next[0] = 0;
            int j = 0;
            for(int i = 1; i < lenP; i++) {
        
                while(j > 0 && pattern.charAt(j) != pattern.charAt(i))
                    j = next[j - 1];
                if(pattern.charAt(j) == pattern.charAt(i))
                    j++;
                next[i] = j;
            }
            j = 0;
            int lenT = text.length();
            for(int i = 0; i < lenT; i++) {
        
                while(j > 0 && pattern.charAt(j) != text.charAt(i))
                    j = next[j - 1];
                if(pattern.charAt(j) == text.charAt(i))
                    j++;
                if(j == lenP)
                    return i - lenP + 1;
            }
            return -1;
        }
    }

# 四、参考文档 #

1.[「代码随想录」KMP算法详解][KMP 1]  
非常感谢这位博主，我终于会写KMP算法了！！！

> 希望本篇博客也能让小伙伴们掌握KMP算法，写作不易，还望点赞、评论、收藏和关注哈。

[KMP]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[2021052419071661.png]: /images/20221014/bd7cd2af8dcb4b63afc6e8a233417702.png
[20210524192756560.png]: /images/20221014/b18a6503e16a4316bacbe9445b64bed9.png
[20210524222553862.png]: /images/20221014/7120ac78461249d8ab3753933c11af2a.png
[20210524223830986.png]: /images/20221014/5b7a63d9a4644d3696540bc06aec1db6.png
[20210524225314296.png]: /images/20221014/1d3605a8bbb34ebca43498555b03e119.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221014/f5806bf1dbad43df9a82516e428e7eb2.png
[28. _ strStr]: https://leetcode-cn.com/problems/implement-strstr/
[KMP 1]: https://leetcode-cn.com/problems/implement-strstr/solution/bang-ni-ba-kmpsuan-fa-xue-ge-tong-tou-ming-ming-ba/