python实现KMP算法

  1. 求next数组
  2. KMP算法
  3. 参考

学习完KMP算法才发现编程如此的奇妙

求next数组

def getNext(s):
    '''
    计算字符串的next数组
    '''
    length = len(s)
    next = [0 for i in range(length)]
    next[0] = -1
    k = -1
    j = 0
    while j < length-1:
        # 这个 or 逻辑写的np
        if k == -1 or s[j] == s[k]:
            j += 1
            k += 1
            next[j] = k
        else:
            k = next[k]
    return next

从这张图可以看到整个的匹配过程,如果 $p_{k}$ 和 $p_{j}$ 匹配不上,那么就去看 $p_{next[k]}$ 和 $p_{j}$

比如

p = "ABCDABD"

得到的结果就是

[-1, 0, 0, 0, 0, 1, 2]

细节感觉还是要靠自己体会

KMP算法

def KMP(s,p):
    next = getNext(p)

    m,n = 0,0
    while m < len(s) and n < len(p):
        if n == -1 or p[n] == s[m]:
            n += 1
            m += 1

        else:
            n = next[n]
    if n == len(p):
        return True
    else:
        return False

从头开始匹配即可,遇到匹配不上的情况就返回到 next[k]

参考

https://blog.csdn.net/v_JULY_v/article/details/7041827


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论

文章标题:python实现KMP算法

文章字数:238

本文作者:prontosil

发布时间:2020-04-22, 20:23:39

最后更新:2020-04-25, 17:22:34

原始链接:http://prontosil.com/posts/9bd3a30d/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录