是否存在具有不同 space 复杂度的多种 KMP 算法方法？有什么不同？
Are there multiple KMP algorithmic approaches with different space complexities? What is the difference?
我正在阅读 KMP substring search 算法，我在网上找到的示例使用一维 table 来构建前缀信息 table。
我还阅读了 Sedgewick 的解释，他使用二维数组构建 table 并明确指出 KMP 的 space 复杂度是 O(RM)，其中 R 是字母表大小和 M 模式大小，而在其他任何地方都指出 space 复杂性只是 O(M + N) 即要处理的文本和模式大小本身。
所以我对区别感到困惑。是否有多种 KMP 算法方法？他们有不同的范围吗？或者我错过了什么？
一维也能解决子串问题，为什么还需要二维？
我猜 Sedgewick 想要演示 KMP 的变体，它构建了该术语标准意义上的确定性有限自动机。这是一个奇怪的选择（如您所见）使 运行 时间膨胀，但也许有一个我不欣赏的令人信服的教学原因（然后我的博士学位又是关于算法的，所以......）。我会找到另一个更接近原始描述的描述。
我正在阅读 KMP substring search 算法，我在网上找到的示例使用一维 table 来构建前缀信息 table。
我还阅读了 Sedgewick 的解释，他使用二维数组构建 table 并明确指出 KMP 的 space 复杂度是 O(RM)，其中 R 是字母表大小和 M 模式大小，而在其他任何地方都指出 space 复杂性只是 O(M + N) 即要处理的文本和模式大小本身。
所以我对区别感到困惑。是否有多种 KMP 算法方法？他们有不同的范围吗？或者我错过了什么？
一维也能解决子串问题，为什么还需要二维？
我猜 Sedgewick 想要演示 KMP 的变体，它构建了该术语标准意义上的确定性有限自动机。这是一个奇怪的选择（如您所见）使 运行 时间膨胀，但也许有一个我不欣赏的令人信服的教学原因（然后我的博士学位又是关于算法的，所以......）。我会找到另一个更接近原始描述的描述。