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

EN

KMP匹配算法基于finite automata，其工作原理是隐式地为匹配字符串的自动机构建转换表。使用对要搜索的字符串进行非常巧妙的线性时间预处理，可以构建匹配自动机，然后可以在线性时间内对要搜索的字符串模拟该自动机。最终结果是用于字符串匹配的线性时间算法。

构建的自动机的工作原理是，到目前为止，每个匹配的字符串都有一个状态。默认情况下，转换是这样的:匹配下一个字符前进到机器中的下一个状态，并读取无效字符转换回到开头。然而，要搜索的字符串的某些部分可能共享一些重叠的结构，因此添加了一些新的转换，使自动机在读取字符时返回到较早的(但不是第一个)状态。

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

我的包含了对算法如何工作的实际细节的广泛讨论，包括正确性证明，算法背后更正式的直觉，以及如何从第一原理推导算法的解释。我花了一段时间来整理，但我希望这可能是一个很好的资源，可以学习更多关于算法的知识。

希望这能有所帮助！

Morris从第一原理中发现了该算法，但Knuth独立地了解到了Stephen A.库克的一个定理，即确定性的双向下推自动机可以在线性时间内模拟，并通过将模拟专门用于字符串匹配自动机来提取"KMP“的早期版本。普拉特对效率的提高做出了贡献。参见Knuth's retelling。