什么时候用KMP算法好？

Question

我知道 KMP 算法依赖于有类似于后缀的前缀的辅助数组。当上述条件不满足时，它不会有效，因为在辅助数组中包含全零。运行时间是 O(m + n) 吗？如果我是对的，在这种情况下什么是更好的子串算法？

Answer 1

要了解 KMP 何时是一个很好的算法，问“有什么替代方案？”这个问题通常会很有帮助。

KMP 有一个很好的优势，它可以保证最坏情况下的效率。预处理时间总是O(n)，搜索时间总是O(m)。没有最坏情况的输入，没有倒霉的可能性等。如果您在非常大的字符串（大 m）中搜索非常长的字符串（大 n），与其他算法相比，这可能是非常可取的，例如朴素的（在坏情况下可能需要时间 Θ(mn)）、Rabin-Karp（病理输入可能需要时间 Θ(mn)）或 Boyer-Moore（最坏情况可能是 Θ(mn)）。您是对的，在字符串没有很多重叠部分的情况下，KMP 可能不是那么必要，但是您永远不需要担心是否存在坏情况的事实绝对是一件好事！

KMP 还有一个很好的特性，即处理可以一次完成。如果您知道要多次搜索相同的子字符串，则可以执行一次 O(n) 预处理工作，然后就可以在 O(O) 时间内搜索您想要的任何长度为 m 的字符串（米）。