是否存在多种具有不同空间复杂度的KMP算法?有什么区别? [英] Are there multiple KMP algorithmic approaches with different space complexities? What is the difference?

问题描述

我正在阅读有关 KMP子字符串搜索算法和我在网上找到的示例都使用一维表来构建前缀信息表.
我还阅读了Sedgewick的说明，他使用2维数组构建表，并明确指出KMP的空间复杂度为 O(RM)，其中 R 是字母大小和 M 模式大小，而其他所有地方都指出空间复杂度仅为 O(M + N)，即要处理的文本和模式大小本身.
所以我对区别感到困惑.是否有多种KMP算法方法?它们有不同的范围吗?还是我想念什么?
如果一维也可以解决子串问题，为什么需要二维?

I am reading about the KMP substring search algorithm and the examples I find online use an one-dimensional table to build the prefix information table.
I also read the Sedgewick explanation and he used a 2-D array to build the table and explicitly states that the space complexity of KMP is O(RM) where R is the alphabet size and M the pattern size while everywhere else it is stated that the space complexity is just O(M + N) i.e. the text to process and the pattern size itself.
So I am confused on the difference. Are there multiple KMP algorithmic approaches? And do they have different scope? Or what am I missing?
Why is the 2D needed if 1D can solve the substring problem too?

推荐答案

我猜Sedgewick想要演示KMP的一种变体，它以该术语的标准含义构造了确定性有限自动机.(您所观察到的)膨胀运行时间是一个奇怪的选择，但是也许有一个令人信服的教学原因，我对此并不感激(然后我的博士学位是关于算法的，所以...).我会发现另一个更贴近原始说明的描述.

I guess Sedgewick wanted to demonstrate a variant of KMP that constructs a deterministic finite automaton in the standard sense of that term. It's a weird choice that (as you observe) bloats the running time, but maybe there was a compelling pedagogical reason that I don't appreciate (then again my PhD was on algorithms, so...). I'd find another description that follows the original more closely.

这篇关于是否存在多种具有不同空间复杂度的KMP算法?有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！