美文网首页
图解kmp算法-通俗易懂kmp算法

图解kmp算法-通俗易懂kmp算法

作者: MrBryan | 来源:发表于2019-10-18 15:45 被阅读0次

    最近研究了一下kmp算法(Knuth-Morris-Pratt),百度了好多帖子,看的稀里糊涂。为了自己可以简单理解(还有最重要的next数组),也为了自己以后忘记的话不用再满世界百度,索性将自己的理解记录下来

    用途

    KMP算法,具体谁发明的就不说了,它主要的用途就是查找字符串,查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。换句话说,就是查找字符串"abc"是否包含字符串"ab",如果包含,返回包含的起始位置
    如下两个字符串:

    str = "dabxabxababxabwabxad" (待查找字符串)
    ptr = "abxabwabxad" (目标字符串)
    
    

    需要计算str中是否含有ptr,如果有,返回str中出现的起始位置,如果没有,返回-1
    通过肉眼观察我们发现,str中是包含ptr的
    dabxabxababxabwabxad,ptr是在str中第9位(下标从0开始)开始出现的,那么返回的结果就是9

    实现

    先看一下go的实现代码(只是为了方便才用go实现,使用map生成的next数组效率很低)

    func main() {
        str := "dabxabxababxabwabxad"
        ptr := "abxabwabxad"
        i := kmp(str, ptr)
        fmt.Println(i)
    }
    
    func next(findStr string, num int) (next map[int]int) {
        k := 0
        next = make(map[int]int, num)
        next[0] = k
        for i := 1; i < num; i++ {
            for k > 0 && findStr[k] != findStr[i] {
                k = next[k-1]
            }
            if findStr[k] == findStr[i] {
                k++
            }
            next[i] = k
        }
        return next
    }
    
    func kmp(str string, findStr string) int {
        strL := len(str)
        findStrL := len(findStr)
        k := 0
        nextArr := next(findStr, findStrL)
        for i := 0; i < strL; i++ {
            for k > 0 && findStr[k] != str[i] {
                k = nextArr[k-1]
            }
            if findStr[k] == str[i] {
                k++
            }
            if k == findStrL {
                return i - k + 1
            }
        }
        return -1
    }
    
    

    算法由两部分组成
    1、计算ptr每一位及之前的字符串中,前缀和后缀公共部分的最大长度的next数组
    2、匹配ptr和str,当ptr失配时,利用next数组,实现ptr的最大后移,从而避免不必要的匹配,减少匹配次数
    by smoke_zl

    计算next数组

    前缀和后缀公共部分的最大长度

    一个字符串ababa,他的前缀是可以是a,ab,aba,abab(不包含最后一位),后缀是a,ba,aba,baba(不包含第一位)
    前缀后缀公共部分就是aaba,公共部分最大就是aba,公共部分的最大长度就是3

    next数组

    next数组是ptr每一位及之前的字符串中,前缀和后缀公共部分的最大长度的集合
    比如ptr字符串的长度是11(abxabwabxad),那么next数组就有11个元素

    • next[0]表示ptr前一位a中,前缀和后缀公共部分的最大长度,由于a中没有前缀和后缀,所以next[0]=0
    • next[1]表示ptr前两位ab中,前缀和后缀公共部分的最大长度,ab的前缀是a,后缀是b,没有公共部分,所以next[1]=0
      同理
    • next[2]=0(abx中无公共前后缀)
    • next[3]=1(abxa公共前后缀最长为a,长度为1)
    • next[4]=2(abxab公共前后缀最长为ab,长度为2)
    • next[5]=0(abxabw中无公共前后缀)
    • next[6]=1(abxabwa公共前后缀最长为a,长度为1)
    • next[7]=2(abxabwab公共前后缀最长为ab,长度为2)
    • next[8]=3(abxabwabx公共前后缀最长为abx,长度为3)
    • next[9]=4(abxabwabxa公共前后缀最长为abxa,长度为4)
    • next[10]=0(abxabwabxad中无公共前后缀)
    下面用图文来解释,next函数是如何计算next数组的值的
    image

    上图第一行,左边i值为ptr下标的值,中间是ptr字符串的每一位,右边是对应的next[i]值,从 i = 0 开始,分析每一行的计算过程

    • i = 0
      由于字符串的前一位只有一个字符,是没有前后缀的,所以next[0] = 0,对应代码
    k := 0
    next[0] = k
    
    
    • i = 1
      从上一次循环,可知 k = 0,既不满足代码中 k > 0 && findStr[k] != findStr[i]的判断,也不满足 findStr[k] == findStr[i]的判断,所以最后next[i] = k,也就是next[1] = 0

    • i = 2
      同上,k = 0,next[2] = 0

    • i = 3
      k = 0,满足findStr[k] == findStr[i]的判断,执行k++,这时 k = 1,最后next[i] = k,也就是next[3] = 1

    • i= 4
      k = 1, 满足findStr[k] == findStr[i]的判断,执行k++,这时 k = 2,最后next[i] = k,也就是next[4] = 2

    • i = 5
      k = 2,满足 k > 0 && findStr[k] != findStr[i],执行k = next[k-1],k = next[2-1] = next[1] = 0
      很多人(包括我)都很不理解k = next[k-1]这行代码的意思,这里先不做解释,后边 i = 10 的时候说

    • i = 6...i = 9
      i = 6 到 i = 9 的逻辑和上边相似,就不重复说了,可以参照着图看

    • i = 10
      k = 4,满足 k > 0 && findStr[k] != findStr[i],执行k = next[k-1],在这里仔细说下k = next[k-1]的意思
      当 i = 9 执行完后,字符串指针为下图的样子,此时前后缀公共部分的最大字符串为abxa

      image

      再看abxa字符串,abxa字符串的前后缀公共部分的最大字符串为a,所以 i = 9 时,前后缀公共部分可以分解为下图的形式

      image

      所以当 i = 10 时,如果k > 0 && findStr[k] != findStr[i],也就是 k指向的b不等于i指向的d,如图

      image

      那么k指针就会执行k = next[k-1]回到前缀的公共前缀继续比较,也就是

      image

      这样,就保证最效率的匹配

    匹配字符串

    第一部分利用next函数得到了next数组,下一步执行kmp函数,对ptr和str进行匹配,并当ptr和str失配时,利用next数组,进行最大位移,由于kmp函数和next函数差不多,这里就不详细讲了,直接上图

    image

    参考:
    http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
    https://blog.csdn.net/qq_30974369/article/details/74276186

    相关文章

      网友评论

          本文标题:图解kmp算法-通俗易懂kmp算法

          本文链接:https://www.haomeiwen.com/subject/fuloectx.html