string - 是否存在具有不同空间复杂度的多种 KMP 算法方法？有什么区别？

Question

我正在阅读有关KMP 子字符串搜索算法的信息，并且我在网上找到的示例使用一维表来构建前缀信息表。
我还阅读了 Sedgewick 的解释，他使用二维数组来构建表格并明确指出 KMP 的空间复杂度O(RM)是R字母大小和M模式大小，而在其他任何地方都表示空间复杂度只是O(M + N)即要处理的文本和图案大小本身。
所以我对差异感到困惑。是否有多种 KMP 算法方法？他们有不同的范围吗？或者我错过了什么？
如果一维也能解决子串问题，为什么还需要二维呢？

标签： stringalgorithmsubstringspace-complexityknuth-morris-pratt

Answer 1

我猜 Sedgewick 想演示 KMP 的一种变体，它在该术语的标准意义上构造一个确定性有限自动机。这是一个奇怪的选择，（正如您所观察到的）会增加运行时间，但也许有一个我不欣赏的令人信服的教学原因（然后我的博士学位又是关于算法的，所以......）。我会找到另一个更接近原文的描述。