KMP算法

算法目录

什么是KMP

该算法由三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP

核心思想

当字符不匹配时，你已经知道了之前匹配成功的部分字符，所以不需要再重新匹配这些字符。

算法步骤：

1. 构建失效函数（也叫做前缀数组、部分匹配数组或前缀表）: 这个函数用于告诉你当字符串失配时，下一次比较应从何处开始。数组中的每一个元素都代表了在当前索引处失配时，需要回退到模式串的哪个位置。
   例如，模式串 "ABCDABD" 的失效函数为 [0, 0, 0, 0, 1, 2, 0]

2. 进行模式匹配:

   1. 用两个指针分别遍历文本串和模式串。
   2. 如果字符匹配，则两个指针都前进一步。
   3. 如果字符不匹配，并且模式串的指针不在起始位置，那么将模式串的指针移动到失效函数告诉你的位置。
   4. 如果字符不匹配，并且模式串的指针在起始位置，那么只移动文本串的指针。

优点：

• KMP 算法不需要回溯文本串的指针，这使得它比暴力搜索更高效。
• 文本串的指针永远不会回溯，最坏的情况下，KMP 算法的时间复杂度是 O(N)，其中 N 是文本串的长度。

失效函数构建

def build_failure_function(pattern):
    m = len(pattern)
    # 初始化前缀表，长度与模式串相同
    failure_function = [0] * m
    
    # 用于计算当前前缀表项的变量
    # 初始时设置为 0，因为长度为 1 的子串没有前后缀
    j = 0
    
    # 从模式串的第二个字符（索引 1）开始循环到最后一个字符
    for i in range(1, m):
        # 当前字符与 j 指向的字符不匹配时，需要回溯
        # 这里用 j 来更新前缀表，并同时保持 j 为之前计算过的最长前缀的长度
        while j > 0 and pattern[j] != pattern[i]:
            j = failure_function[j-1]
        
        # 如果当前字符与 j 指向的字符匹配，则 j 增加 1
        if pattern[j] == pattern[i]:
            j += 1
        
        # 将计算得到的最长前缀的长度存储在前缀表的相应位置
        failure_function[i] = j
    
    return failure_function

# 测试代码
pattern = "ABCDABD"
print("Pattern:", pattern)
print("Failure function:", build_failure_function(pattern))

这里 failure_function[i] 存储的是 pattern[0:i+1] 的最长公共前后缀的长度。在这个例子中，对于模式串 "ABCDABD"，输出的失效函数是 [0, 0, 0, 0, 1, 2, 0]。