Python中KMP算法的实现

Question

我见过这个算法的几个实现，例如有两个计数器和前缀上的迭代的实现，或者使用递归的实现。但是，我在理解使用动态规划的方法时有一些困难。你知道吗

由于我的知识浅薄，这就是我想出来的：

def sufperf(S):
    Pi = [0 for i in range(len(S))]
    for i in range(1, len(S)):
        p = Pi[i - 1]
        while p > 0 and S[i] != S[p]:
            p = Pi[p-1]
        if S[i] == S[p]:
            p += 1
        Pi[i] = p
    return Pi


def KMP(S, subS):
    NewS = subS + "#" + S
    SuperS = sufperf(NewS)
    k = 0
    for i in SuperS:
        if i == len(subS):
            k += 1
    return k

我完全理解KMP函数中的逻辑有些困难。 有人能帮忙吗？你知道吗

Answer 1

使用关于字符串的知识基本上是所有字符串搜索算法的基础，你已经知道关于字符串的一些东西，如果你愿意，你可以尝试利用这个“启发式”来节省自己的搜索时间。你知道吗

KMP特别利用了这样一个事实：如果我们知道后缀与前缀匹配。在这个例子中，我们在var haystack中寻找var needle

String we're looking for (Needle) abczabcd 12345678

String we're looking in (Haystack) abcz abcb a b c d a b c z 1234 5678 9 10 11 12 13 14 15 16 -> indices

我们穿过abczabcb，然后我们击中b（草堆的索引10），而不是d（针的索引8）。你知道吗

使用KMP中的这个后缀/前缀规则，我们不必一直返回到b来搜索abc，相反，我们可以利用abcb具有前缀abc的事实，并开始在b处检查它是否等于z。你知道吗

这并不是说我们可以跳过abczabcb，而不必从索引2、3、4、5、6、7、8中再次搜索要查找的字符串

我个人非常喜欢BacktoBackSWE的youtube频道，他对KMP的解释非常清晰易懂。你知道吗

资源：

https://www.youtube.com/watch?v=BXCEFAzhxGY

https://medium.com/@pivincii/pattern-searching-algorithm-knuth-morris-pratt-aka-kmp-algorithm-13f4a9fd968b

另一个字符串搜索算法Boyer-Moore使用好后缀和坏字符规则。我提到这一点是因为我认为这是一个很好的观察，所有这些字符串匹配算法在使用有关字符串的知识的意义上是相似的。你知道吗

维基百科对此进行了更深入的探讨：

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Shift_rules

Geeksforgeks在这方面也有很好的资源：

https://www.geeksforgeeks.org/boyer-moore-algorithm-good-suffix-heuristic/

https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/