[第 5 期] 算法精选-你应该知道的 KMP 算法

[zzzzzzggggggg]

本期讲讲 KMP 算法，也就是江湖俗称的<del>看毛片</del>算法。

这个算法其实在面试中出现的概率还是蛮大的，不管是校招还是社招，甚至在考研中也遇到过，而且 KMP 算法也比较难理解，所以很有必要研究一下。

KMP 要解决的问题

先说一下这个算法出现的背景，也就是解决什么问题。每个算法和框架都有它出现的原因和要解决的问题，很多时候你不会一个技术，并不是你笨，而是你没有找到它的使用场景或者是没搞明白它要解决的问题而已。所以，了解它要解决的问题，是学习的重中之重。

首先看一个例子：

字符串 str="abcabcabcde"，字符串 match="abcabcde"

如果 str 包含子串 match，返回 match 在 str 中的起始位置。

这个问题其实可以使用暴力来破解，如下图：

从 str[i]开始（ i 初始等于 0 ），每次只要遇到了 match 和 str 不匹配的情况，str 回退到 str[i+1]，再继续 str[i+1]和 match[0]依次对比，长此以往，直到 match 完全匹配出来或者 str 遍历完毕为止，这样做的时间复杂度是 O(M*N)，M 是 str 的长度，N 是 match 的长度。

那么有没有种方法可以不这么笨拙的解决字符串匹配的问题呢？

KMP 算法就是解决 match 和 str 在匹配过程中不停的做回退的问题的。简单一句话，KMP 算法是做字符串高效匹配的算法

KMP 算法是如何做的

说 KMP 的解法之前，先看看一个聪明的人类是如何解决这个问题的：

这样做的原因是没必要一次性退回从 match[0]和 str[1]开始比较，因为可以看出来绿色框内的 match[0,1,2]和 str[3,4,5]是重合的，重合的这部分完全可以复用，没有必要再从 match[0]和 str[1]开始重复比较；

具体的过程可以模拟抽象成下图：

所以问题转化成了：

每次 str[j]和 match[j]不相同时，在 match[0...j-1]这段字符串中，以 match[j-1]结尾的后缀子串（不能包含 match[0]）和以 match[0]开头的前缀子串（不能包含 match[j-1]）的最大匹配长度是多少？只要求出这个最大匹配长度，就能在 str[j]和 match[j]不相同时，知道把 match 滑动到什么位置了！

KMP 算法的重点就是维护一个数组，保存 match 中每个字符在不匹配时，match 应该滑动到什么位置，这个数组起名叫 next。

如何构造 next 数组

那么如何构造 next 数组呢？

首先对于 match[0]来说，它前面没有字符，所以 next[0]规定为-1 ；对于 match[1]来说，因为 next 数组规定计算的时候子串后缀不能包含第一个字符，所以 next[1]=0 ；

说完特殊情况，再说说常规情况，比如现在假设 match[i]是 A 字符，match[i-1]是 B 字符，可以通过 next[i-1]得到 B 字符前的字符串最长前缀与后缀的匹配区域，现在假设 L 为最长前缀子串，K 为最长后缀子串，C 为最长前缀子串之后的一位字符，现在只需要比较 C 和 B 即可

1. 如果字符 B 等于字符 C，那么 A 字符之前的字符串的最长前缀与后缀匹配区域就可以确定了，最长匹配前缀子串为 L+C，最长匹配后缀子串为 K+B，next[i] = next[i-1]+1 ；
2. 如果字符 B 不等于字符 C，就看 C 字符之前的前缀后缀匹配问题。假设 C 的位置是 match[cn]，那么可以通过 next[cn]得到字符 C 前的字符串的最长匹配前缀是 M，最长匹配后缀是 N，再假设 M 后面一位字符是 D，又因为 L=K，所以同等位置的 p=N ；接下来就是比较一下 B 和 D 是否相同，如果 B=D，那么 A 字符之前的字符串最长匹配前缀子串是 M+D，最长匹配后缀子串是 P+B，如果不相同的话，照着之前说的思路继续往前跳，直到跳到 match[0]

代码如下

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(str, match) {
    if(str === null || match === null || match.length > str.length)
        return -1;
    if(str === "")
        return 0;
    
    let index1 = 0;
    let index2 = 0;
    let nextArr = getNext(match);
    console.log(nextArr);
    while(index1 < str.length && index2 < match.length) {
        if(str[index1] === match[index2]) {
            index1++;
            index2++;
        } else if(nextArr[index2] === -1) {
            index1++;   
        } else {
            index2 = nextArr[index2];
        }
    }
    
    return index2 === match.length ? index1 - index2 : -1;
};

var getNext = function(match) {
    let next = [-1, 0];
    
    let cn = 0;
    let index = 2;
    
    while(index < match.length) {
        if(match[index-1] === match[cn]) {
            cn++;
            next[index] = cn;
            index++;
        } 
        else if(cn > 0) {
            cn = next[cn];
        } 
        else {
            next[index] = 0;
            index++;
        }
    }
    
    return next;
}

感兴趣可以关注我的公众号——前端亚古兽

Java版解法

class Solution {
    public int strStr(String str, String match) {
        if(str == null || match == null || str.length() < match.length()) {
            return -1;
        }
        
        if(str.length() < 1) {
            return 0;
        }
        
        char[] strs = str.toCharArray();
        char[] matches = match.toCharArray();
        
        int index1 = 0;
        int index2 = 0;
        
        int[] next = getNextArr(matches);
        while (index1 < strs.length && index2 < matches.length) {
            System.out.println(index2);
            if(strs[index1] == matches[index2]) {
                index1++;
                index2++;
            } else if(next[index2] == -1) {
                index1++; 
            } else {
                index2 = next[index2];
            }
        }
        
        return index2 == matches.length ? index1 - index2 : -1;
    }
    
    public int[] getNextArr(char[] match) {
        if(match.length == 1) {
            return new int[] {-1};
        }
            
        int[] next = new int[match.length];
        next[0] = -1;
        next[1] = 0;
        
        int index = 2;
        int cn = 0;
        while(index < match.length) {
            if(match[index-1] == match[cn]) {
                cn++;
                next[index] = cn;
                index++;
            } else if(cn > 0) {
                cn = next[cn];
            } else {
                next[index] = 0;
                index++;
            }
        }
        return next;
    }
}

[zzzzzzggggggg]

个人觉得还是讲的很清楚的

[zzzzzzggggggg]

up

[ericgui]

@zzzzzzggggggg 有 java 版本的实现么？

[lewis89]

@ericgui #3 你在朴素的基础上 改造一下 构建好 next 数据就好了

[WhatIf]

想起当年读书时候自学数据结构，书上介绍这个算法，花了一周以上时间才明白说的是什么，后来又是忘得差不多了。再后来，看到这个算法时候，却觉得是自然而然的

[zzzzzzggggggg]

@WhatIf 对，有的时候就是那一瞬间就悟了

[zzzzzzggggggg]

@ericgui 有的，今天我补充一个 Java 版本的

[zzzzzzggggggg]

@ericgui 老铁可以看下，我补充了 Java 的解法，好久没写 Java 了语法不太熟悉，还请担待

[ericgui]

@zzzzzzggggggg

if(str.length() < 1) {
return 0;
}


改成 if (str.length == 0 || p.length() == 0) return 0;

那不然会有一个 corner case 报错

corner case 是 => str = ""; match = "";

[zzzzzzggggggg]

@ericgui 好嘞，确实忽略了 match 也是空字符串的 case

[ericgui]

@zzzzzzggggggg 我也是用这算法上 leetcode 试了试，才发现有 corner case

[zzzzzzggggggg]

@ericgui 是国内版的还是国外版的 LeetCode，我在国内版的试了下是可以通过的😅

[ericgui]

@zzzzzzggggggg 英文版，28 题

[zzzzzzggggggg]

@ericgui 好嘞