03. KMP 算法

[utterances-bot]

03.KMP 算法 | 算法通关手册

KMP 算法 # 1. KMP 算法介绍 # KMP 算法：全称叫做 「Knuth Morris Pratt 算法」，是由它的三位发明者 Donald Knuth、James H. Morris、 Vaughan Pratt 的名字来命名的。

https://algo.itcharge.cn/06.String/02.String-Single-Pattern-Matching/03.String-KMP/

[zwei2016]

Thanks a lot for sharing KMP algorithm.
有一个问题就是： next数组中前缀和后缀是有可能互相重叠的，如果按照所给的实现。比如 p = 'abcabcabc' 对应的next = [0,0,0,1,2,3,4,5,6]. 其中 ‘abcabc’是一个重叠的前缀和后缀。请问这个对结果有没有什么影响？

[ZhiqiJiang]

# 生成 next 数组
# next[j] 表示下标 j 之前(包含j)的模式串 p 中，最长相等前后缀的长度
# 求解最长相等前后缀的长度 等价于 在文本串p[1:right]中匹配模式串p[:right-1]，和 在T中匹配p 类似。
def generateNext(p: str):
    m = len(p)
    next = [0 for _ in range(m)]                # next[0]为0，所以初始化数组元素全部为0
    
    left = 0                                    # 前缀串从0开始
    for right in range(1, m):                   # 后缀串从1开始
        while left > 0 and p[left] != p[right]: # 匹配不成功, left 进行回退, left == 0 时停止回退
            left = next[left - 1]               # left 进行回退操作
        if p[left] == p[right]:                 # 匹配成功，找到相同的前后缀，先让 left += 1，此时 left 为前缀长度
            left += 1
        next[right] = left                      # 记录前缀长度，更新 next[right], 结束本次循环, right += 1

    return next

[itcharge]

Thanks a lot for sharing KMP algorithm. 有一个问题就是： next数组中前缀和后缀是有可能互相重叠的，如果按照所给的实现。比如 p = 'abcabcabc' 对应的next = [0,0,0,1,2,3,4,5,6]. 其中 ‘abcabc’是一个重叠的前缀和后缀。请问这个对结果有没有什么影响？

对结果没有影响。对匹配过程会有影响，理论上前缀和后缀长度越长，子串的重复部分越多，所能跳过的字符也就越多。

[Yiniau]

是不是可以这么理解：当适配发生在 j 时，把 p[0, j] 中的 前缀位置直接移动到后缀位置 来减少操作