string - 什么时候使用 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) 预处理工作，然后能够及时搜索您想要的任何长度为 m 的字符串 O (米)。