string - KMP模式匹配算法背后的理论是什么？

Question

KMP模式匹配算法的理论基础是什么？

我了解算法本身，但不明白 Knuth、Morris 和 Pratt 是如何发明这种算法的。

有数学证明吗？

请问可以给个链接吗？

Answer 1

KMP 匹配算法基于有限自动机，并通过为匹配字符串的自动机隐式构建转移表来工作。使用非常巧妙的对要搜索的字符串进行线性时间预处理，可以构建匹配的自动机，然后可以在字符串上模拟自动机以线性时间进行搜索。最终结果是用于字符串匹配的线性时间算法。

构建的自动机通过为到目前为止已匹配的字符串的每个数量设置一个状态来工作。默认情况下，转换是这样的，匹配下一个字符前进到机器中的下一个状态，读取无效字符转换回到开头。但是，要搜索的字符串的某些部分可能共享一些重叠结构，因此添加了一些新的转换，当读取一个字符时，这些转换将自动机返回到较早的（但不是第一个）状态。

该算法由 Aho-Corasick 算法推广，该算法构建了一个更复杂的自动机，以便一次搜索多个字符串。

我在我的个人网站上有一个该算法的实现，其中包含对该算法如何工作的实际细节的广泛讨论，包括正确性证明、算法背后的更正式的直觉，以及如何从第一原理推导出算法的解释。我花了一些时间来整理，但我希望它可能是一个很好的资源来了解更多关于算法的信息。

希望这可以帮助！

Answer 2

Morris 从第一原理中发现了该算法，但 Knuth 独立学习了 Stephen A. Cook 提出的一个定理，即确定性双向下推自动机可以在线性时间内进行模拟，并通过将模拟专门用于字符串匹配自动机。Pratt 有助于提高效率。参见Knuth 的复述。