KMP 算法

首先贴出本人写的KMP算法,本人习惯next数组的第一位存的是-1,下面是代码:

def KMP(txt, pat):
    if pat == "": return 0
    def get_next_arr(pat):
        next_arr, j, k =[-1], 0, -1
        while j < len(pat) - 1:
            if k == -1 or pat[j] == pat[k]:
                k, j = k + 1, j + 1
                next_arr.append(k)
            else:
                k = next_arr[k]
        return next_arr

    next_arr = get_next_arr(pat)

    i, j = 0, 0
    while i < len(txt) and j < len(pat):
        if j == -1 or txt[i] == pat[j]:
            i, j = i + 1, j + 1
        else:
            j = next_arr[j]
    if j == len(pat):
        return i - j
    return -1

KMP代码关键有两个部分

首先是求解next数组,next数组记录的内容是pat中字串的最长相同前后缀的长度,这个数据需要先求出来,方便后续的字符串匹配处理。next数组求解过程中的k=next[k]这个步骤不太好理解,详细可以参考文章,或者视频

第二点就是在匹配主串的过程,其中需要借助next数组进行巧妙的指针变化,主串的指针可以实现不回退。 KMP算法的时间复杂度是O(n+m)

发表评论

电子邮件地址不会被公开。 必填项已用*标注