字符串-KMP算法详解-图文教程

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

KMP算法

内容:

该算法为了解决对字符串匹配问题求解

查找在一个字符串中 是否包含另外一个字符串，

我们把第一个字符串称为主串，第二个称为模式串

常规思路(暴力解法):

用两层for循环来暴力求解，时间复杂度用时O(n*m) 即为二者长度的乘积

代码如下:

class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()) return -1;
        int index = -1;
        int j = 0;
        for(int i = 0 ; i < haystack.length() ; i++) {
            if(haystack.charAt(i) == needle.charAt(j)) {
                index = i;
                while(j<needle.length()) { 
                //第二层for
                    if(i >= haystack.length()) {
                        return -1;
                    }
                    if(haystack.charAt(i) != needle.charAt(j)) {
                        i = index;
                        j = 0;
                        index = -1;
                        break;
                    }
                    i++;
                    j++;
                }
                if(index != -1) return index; 

            }
        }
        return index;
    }
}

这样的解法没什么问题，但是很费事，如果一旦二者字符串长度增大，效率就会变得很低.

KMP算法 

既然N^2级别的时间效率较低，我们是否可以想办法降低时间达到O(nlogn)级别，甚至是到O(n)级别呢.

KMP算法就是三位大神所研究的, O(N)级的时间复杂度的算法.

但是在正式进入KMP之前，需要引入一个概念

前缀函数:

假设有一个字符串 ATAATA , 那么它的前缀和后缀如下:

PS.前缀是不包含该字符串自身的.

前缀函数的意义--能让前缀和后缀相等的子串长度的最大值 （上面标红的部分,最大值是3）

 务必理解这个概念,因为这个概念是用来生成 部分匹配表 (next数组) 的关键

KMP算法比起暴力算法优秀的是发现不匹配之后，模式串并不用从头开始匹配，而是根据

部分匹配表(next数组)来跳过一部分的字符 ，可以让主串不回头，继续匹配。

当发现 s[i] != p[j] 的时候, 下一次匹配应该从 p [ next [ j-1 ] ] 开始 , 也就是如图所示的2 ,意味着跳过两个字符

使用 s[i] 跟 p[2] 相比较. 如图2 

这部分的代码

    public int strStr(String haystack, String needle) {
        int j = 0;
        int[] next = getNext(needle); //这里获取next数组
        for(int i = 0 ; i < haystack.length() ; i++) {
            //不相等不改变i的位置,只是去改变j的位置
            while(j>0 && haystack.charAt(i)!=needle.charAt(j)) {
                //根据next数组更新j
                j = next[j-1];
            }
            //相等的话继续移动
            if(haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if(j == needle.length()) {
                return i-j+1;
            }
        }
        return -1;
    }

 好了，现在我们解决了匹配层面的问题，那么最关键的 next数组 怎么得到

换句话来说，只要知道next数组, 之后按个匹配就完事了

next数组:

next数组实质上就是前文提到的前缀函数!

二者是一回事 , 下面称呼前缀函数为 π [i]

那么接下来来根据前缀函数的规则模拟一下next数组的生成

可以见到, 前缀函数生成规则如上图 , 根据前文对于前缀函数的介绍可以轻易得到

下一步是对next数组的生成,其实next数组可以视为π[i]我个人认为没什么区别(仅从数值上来看)

ATAATA的next数组为 [0,0,1,1,2,3]

好的，那么我们来思考一下如何生成上表所示的前缀函数

如图,但是如果是代码为:

int[] next = new int[patt.length()];
next[0] = 0; //无论如何第一个一定为0 因为没有前后缀相等的情况!
for(int i = 1 ; i < patt.length() ; i++){
    int len = next[i-1]; //由图所示,该长度为上一个前缀函数的值 , 是否更新还要分情况
    if(patt.charAt(len) == patt.charAt(i)) {
        next[i] = len+1;
    }
}

 但是更多的是不相同，如果不相同要更新 next[i] 也就是π[i] 需要的是第二长的前缀函数(这里是不准确的，但是大概意思是). 如图所示的 π'

int[] next = new int[patt.length()];
next[0] = 0; //无论如何第一个一定为0 因为没有前后缀相等的情况!
for(int i = 1 ; i < patt.length() ; i++){
    int len = next[i-1]; //由图所示,该长度为上一个前缀函数的值 , 是否更新还要分情况
    if(patt.charAt(len) != patt.charAt(i)) {
       len = next_2nd(i); 
    }
    if(patt.charAt(len) == patt.charAt(i)) {
        next[i] = len+1;
    }
}

 如果第二长还是不行，那么就是第三长，第四长 ... 第n长 ,即为一个循环来解决

int[] next = new int[patt.length()];
next[0] = 0; //无论如何第一个一定为0 因为没有前后缀相等的情况!
for(int i = 1 ; i < patt.length() ; i++){
    int len = next[i-1]; //由图所示,该长度为上一个前缀函数的值 , 是否更新还要分情况
    while(len>0 && patt.charAt(len) != patt.charAt(i)) {
       len = next_nextLength(i); 
    }
    if(patt.charAt(len) == patt.charAt(i)) {
        next[i] = len+1;
    }
}

如何求 第 n 长 的前缀 , 只要解决这个问题，一切问题都迎刃而解了，也就差最后一块拼图

如图, 咱们假设 C 部分是 第 n 长的前缀

由定义 可知 A = C 。

由于两个画框的地方 完全相等 。

那么 , B = C

即为 A = B .

想要拿到第 n 长的 就是求已经求过部分的前缀函数!

这部分理解之后，就可以得到 next_nextLength(i) 完全等于 next [ len - 1 ] 也就是 π [ len-1 ]

好了，那么我们最后写出代码

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

这样可以求得next数组, 我认为next数组可以完全等于前缀函数 next数组只不过是前缀函数的一种体现形式而已。

综上，整理所有的代码可以得到KMP的模板

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

总结:

KMP是前缀函数的一种应用，了解前缀函数然后去构建next数组是KMP的核心内容。

dp思想也是渗透的无孔不入. 在求next最后一部分的时候， 用到的动态规划思想，若是要更新len的值，需要从前面部分获取.

最后是KMP的哲学思想

一个人能走的多快，多远，取决于他对于过去的记忆，是否以往本心。

能吸取过去的教训，不断地迭代，才能永不走回头路，一直向前走!