冲塔KMP算法

不才，学完数据结构快一年了，但这一年里我一直被KMP算法困扰着。去年在课堂上时，关于这个算法我就听的云里雾里，在课后紧张的几分钟里，赶忙抓起教材,希望能够理解这一算法，匆忙翻阅几页，有种想撕书的冲动，暗暗克制住怒火。之后在网上，搜寻了许多资料，但一一读过后总有一种“词不达意”的感觉，遗憾没能深入理解这一算法。

最近在 LeetCode 上碰到了关于字符串的题目，恰巧需要用到KMP算法，于是借此机会重新梳理一下，同时相较于去年，我对这一算法的理解程度也加深了，希望以文章的形式促成我之思想与KMP 算法的完全融合吧。

KMP算法用武之地

KMP算法主要是用于解决字符串匹配问题，若给出两个字符串m和n，需验证n是否是m的子字符串，此时KMP算法就派上用场了。

按照暴力解法，两个字符串分别有指针从头指到尾，一次进行比较，那么时间复杂度为O（m*n）,但使用KMP算法就不必从头指到尾进行比较了。

如上图的两串字符串，当上下指针到当前位置时，发生了不匹配的情况，按照暴力解法，上指针会移动到第二个字符，下指针会移动到首字符。而KMP算法的上指针不变，下指针会移动到b处。

前缀与前缀表

前缀是指包含首字符，不含尾字符的子字符串。

后缀是指包含尾字符，不含首字符的子字符串。

前缀表记录的是以该字符为尾字符的字符串中前缀与后缀相等的最大长度。

next数组

私以为next数组是KMP算法的核心，也是难点，所谓next数组就是前缀表。能否求出一串字符串的next数组是决定KMP算法实现与否的关键一步。

手撸next数组代码

深入理解，有一种递归套娃的感觉，细思极恐！！！

• 初始化指针 j = 0, i = 1

• 两指针所指字符进行比较，会有两种情况

  • 两字符不匹配，此时，j需要回退,并且回退是一个连续的过程，一直回退到满足条件时才停止回退，一个条件是j已经不能再回退了，即j已经到达首字符处，另一个条件是**i和j所表示的字符相等。同时，需要注意回退并不是简单向前移位**而是根据前一个字符next值进行回退，这与文本串、模式串的比较过程有些类似。

  • 两字符匹配，更新i出next值，i和j自增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution{
    public int[] getNext(String s){
        int[] next = new int[s.length()];
     	int j = 0;
        int i = 1;
        next[0] = 0;
        for(; i < s.length(); i++){
            while(s.charAt(i) != s.charAt(j) && j > 0){
                j = next[j - 1];
            }
            if(s.charAt(i) == s.charAt(j)){
                next[i] = ++j;
            }
        }        
    }
}