Knuth-Morris-Pratt字符串匹配算法

Question

Knuth Pratt字符串搜索算法在论文字符串中的快速模式匹配 (SIAM .计算卷6，第2期，1977年6月)中作了描述。算法的初始步骤是计算下一个表，定义如下：

如果我们有一个辅助表，当我们在它的jth字符pattern[j]上检测到不匹配时，它会准确地告诉我们滑动模式的距离，模式匹配过程将有效地运行。让next[j]是模式中的字符位置，在这种不匹配之后应该检查该位置，这样我们就可以相对于文本滑动模式j − next[j]位置。

给出了模式abcabcacab的实例。如果在j=7处有错配：

abcabcacab
abcabca?

然后，模式应该移到右边的3个位置，匹配应该继续与模式的第四个字符：

   abcabcacab
abcabca?

所以next[7] = 4。在某些情况下，我们知道可以完全跳过不匹配的字符，例如，如果j=3存在不匹配：

abcabcacab
abc?

然后，在不匹配之后，应该从字符继续搜索：

    abcabcacab
abc?

这些特例是用next[j] = −1来表示的。

(如果您正在阅读这篇文章，请注意，作者使用从1开始的索引，正如在Fortran中一样，但是Python惯例是使用从0开始的索引，这就是我在这里给出的。)

这是计算下一个表的代码。请复习。

def findPattern(pattern):

    j = -1
    next = [-1] * len(pattern)
    i = 0 # next[0] is always -1, by KMP definition

    while (i+1 < len(pattern)):
        if (j == -1) or (pattern[j] == pattern[i]):
            i += 1
            j += 1
            if pattern[i] != pattern[j]:
                next[i] = j
            else:
                next[i] = next[j]
        else:
            j = next[j]

    return next

if __name__ == "__main__":

    print findPattern("aaaab")
    print findPattern("abaabc")

输出：

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

Answer 1

效率时间复杂度bug

while (i+1 < len(pattern)):

len(pattern)是在每次迭代时计算的，即使它保持不变，这也会使您的时间复杂度( n )慢一些，其中n是len(pattern)。

使用变量修复错误：

pattern_length = len(pattern)

和：

while (i + 1 < pattern_length):