KMP算法，你想知道的都在这里！

2021 年 2 月 24 日
笔记
算法

简洁

我相信很多人都听说过KMP算法(PS：在上数据结构的时候，这个算法自始至终都没想明白)

大家也知道KMP算法是用来寻找目标子串的算法，但是都没有真正搞懂KMP。之前，我也是如此，我疑惑的有：

Next数组中的值是如何定下来的？
得到Next数组以后，又是如何遍历的？

希望这篇文章能对你们有所帮助！

视频推荐

KMP这种算法，单单靠看文章，还是很难弄懂的，结合图像，以及视频的帮助会更容易弄懂。这里我推荐一个视频：KMP算法

个人也是通过这个视频，恍然大悟的。这里还是非常感谢这位作者的分享。

个人总结

通过上述视频，我想大家应该都有一个大概的了解了。该算法我将它划分为两个部分：

求Next数组
匹配字符串

我将分这两个部分进行细致讲解

第一部分

求Next数组是KMP算法的重点，也是难点！想搞懂这部分一定要看视频！一定要看视频！一定要看视频！我觉得上述的视频，将这部分说的很清楚了。这里做一个总结：(视频里将目标子串的第i号位置映射到Next指针的第i+1号位置。我这里根据程序员的习惯，将目标子串的第i号位置映射到Next指针的第i号位置)

我将Next[i]做一下定义：

/*Next[i]表示：
*	如果(substr.charAt(i) != str.charAt(j))，这时候，将i = Next[i]，再进行字符串匹配。
*/

这种表达虽然不严谨，但是我感觉比较直观hhhh。也即：如果目标子串第i个的值与匹配串第j的值不一致的时候，将目标子串向右滑动，滑动到i = Next[i]。

Next[i]值的定义：

/*Next[i]的值为:
*	第0位为头的字符串s1，与第i-1为尾的字符串中s2，寻找他们的最长真子串。
*	真子串：这个真子串，就是s1的长度要小于i-1。因为这两个子串如果是相同的，就没有意义了
*/

上面这两个定义值得细品，这也是KMP的精髓，也正是Next数组，KMP算法才能更加高效！

其中需要注意的点是：Next[0] = 0,Next[1] = 0，因为从第2个开始，s1和s2才有意义。

看完上述定义，我将求Next数组的函数实现出来。注：该函数求Next数组时间复杂度较高，因为是最原始的思路，大家可以想想有什么简化的思路，可以在评论区留言，之后我有时间进行改进

/**
     * 该函数是为了，根据目标子串subStr，求解该子串的Next数
     * @param 目标子串substr
     * @return subStr的Next数组
     */
static int[] CalculateNext(String substr){
    	//init
        int[] Next = new int[substr.length()];
    	//求解Next[i]
        for(int i = 2; i < substr.length(); i++){
            //第0位为头的l字符串，与第i-1为尾的r字符串
            int left = 0; int right = i - 1;
            String l = Character.toString(substr.charAt(left));
            String r = Character.toString(substr.charAt(right));
            int maxLen = 0;
            //当l与r均为真子串的时候
            while(left < i - 1){
                //如果两个字符串相同，说明这是目前最长的公共子串
                if(l.equals(r)) maxLen = l.length();
                left++;
                right--;
                //继续扩大搜索范围
                l = l + Character.toString(substr.charAt(left));
                r = Character.toString(substr.charAt(right)) + r;
            }
            //最终的maxLen即为Next[i]的值
            Next[i] = maxLen;
        }
        return Next;
    }

第二部分

这个部分就简单很多了，只要注意一点小细节，整体思路非常清晰直观：

在保证目标子串与匹配串匹配的过程中，不会越界的情况下：进行目标子串的滑动操作

当subStr.charAt(i) == str.charAt(j)的时候，i与j同时往右移动即可，当完全匹配的时候，就返回

当subStr.charAt(i) ！= str.charAt(j)的时候，i = Next[i]即可。

这里j需要注意一个细节，如果i == 0，需要j往右移一位，因为第一位都不匹配，前面就再也没有能匹配的字符串了。

/**
     * 该函数用于查看目标子串在匹配串中第一次出现的位置
     * @param 目标子串subStr
     * @param 匹配串str
     * @param Next数组
     * @return str中，第一次出现subStr的位置
     */
static int findPosition(String subStr,String str,int[] Next){
        //初始化两个字符串的指针
    	int i = 0;
        int j = 0;
    	//保证目标子串与匹配串匹配的过程中，不会越界
        while(j + subStr.length() - i <= str.length()){
            //当匹配的时候，i与j同时往右移
            if(subStr.charAt(i) == str.charAt(j)){
                i++;j++;
                //当完全匹配的时候，返回
                if(i == subStr.length()) return j - subStr.length();
            }
            //不匹配的时候，匹配串指针j只有在i = 0的时候，才右移动。
            else {
                if(i == 0) j++;
                //i值都需要更新
                i = Next[i];
            }
        }
        return -1;
    }

总结

这里主要探讨的是Next数组，这个是KMP算法的核心！以前考试都是考Next数组的求解，可见Next数组的重要性。

Tags: 算法