V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzzzzggggggg
V2EX  ›  程序员

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

  •  
  •   zzzzzzggggggg · 2020-03-14 22:09:46 +08:00 · 2761 次点击
    这是一个创建于 1475 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本期讲讲 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;
    }
    

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

    第 1 条附言  ·  2020-03-15 11:58:53 +08:00

    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;
        }
    }
    
    14 条回复    2020-03-16 09:48:08 +08:00
    zzzzzzggggggg
        1
    zzzzzzggggggg  
    OP
       2020-03-14 22:19:28 +08:00
    个人觉得还是讲的很清楚的
    zzzzzzggggggg
        2
    zzzzzzggggggg  
    OP
       2020-03-15 06:49:42 +08:00 via iPhone
    up
    ericgui
        3
    ericgui  
       2020-03-15 08:17:19 +08:00
    @zzzzzzggggggg 有 java 版本的实现么?
    lewis89
        4
    lewis89  
       2020-03-15 08:36:51 +08:00
    @ericgui #3 你在朴素的基础上 改造一下 构建好 next 数据就好了
    WhatIf
        5
    WhatIf  
       2020-03-15 09:18:57 +08:00 via Android
    想起当年读书时候自学数据结构,书上介绍这个算法,花了一周以上时间才明白说的是什么,后来又是忘得差不多了。再后来,看到这个算法时候,却觉得是自然而然的
    zzzzzzggggggg
        6
    zzzzzzggggggg  
    OP
       2020-03-15 10:39:06 +08:00
    @WhatIf 对,有的时候就是那一瞬间就悟了
    zzzzzzggggggg
        7
    zzzzzzggggggg  
    OP
       2020-03-15 10:39:28 +08:00
    @ericgui 有的,今天我补充一个 Java 版本的
    zzzzzzggggggg
        8
    zzzzzzggggggg  
    OP
       2020-03-15 11:59:42 +08:00
    @ericgui 老铁可以看下,我补充了 Java 的解法,好久没写 Java 了语法不太熟悉,还请担待
    ericgui
        9
    ericgui  
       2020-03-15 12:02:09 +08:00
    @zzzzzzggggggg

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


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

    那不然会有一个 corner case 报错

    corner case 是 => str = ""; match = "";
    zzzzzzggggggg
        10
    zzzzzzggggggg  
    OP
       2020-03-15 12:50:57 +08:00
    @ericgui 好嘞,确实忽略了 match 也是空字符串的 case
    ericgui
        11
    ericgui  
       2020-03-15 13:37:55 +08:00
    @zzzzzzggggggg 我也是用这算法上 leetcode 试了试,才发现有 corner case
    zzzzzzggggggg
        12
    zzzzzzggggggg  
    OP
       2020-03-15 17:22:46 +08:00
    @ericgui 是国内版的还是国外版的 LeetCode,我在国内版的试了下是可以通过的😅
    ericgui
        13
    ericgui  
       2020-03-16 00:29:03 +08:00
    @zzzzzzggggggg 英文版,28 题
    zzzzzzggggggg
        14
    zzzzzzggggggg  
    OP
       2020-03-16 09:48:08 +08:00
    @ericgui 好嘞
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5276 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 07:18 · PVG 15:18 · LAX 00:18 · JFK 03:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.