什么时候用KMP算法好？
When is good to use KMP algorithm?
我了解到KMP算法依赖于helper数组，其中有类似于后缀的前缀。
当不满足上述条件时，它不会有效，因为在辅助数组中包含全零。
运行时间会是 O(m + n) 吗？
如果我是对的，在这种情况下更好的子串算法是什么？
要了解 KMP 何时是一个很好的算法，提出这个问题通常很有帮助 "what's the alternative?"
KMP 有一个很好的优势，它可以保证最坏情况下的效率。预处理时间总是 O(n)，搜索时间总是 O(m)。没有最坏情况的输入，没有倒霉的可能性等。如果您在非常大的字符串（大 m）中搜索非常长的字符串（大 n），与其他算法相比，这可能是非常可取的，例如朴素的（在糟糕的情况下可能需要时间 Θ(mn)）、Rabin-Karp（病态输入可能需要时间 Θ(mn)）或 Boyer-Moore（最坏的情况可能是 Θ(mn)）。你是对的，在字符串重叠部分不多的情况下，KMP 可能不是那么必要，但事实上你永远不需要担心是否有坏情况，这绝对是一件好事！
KMP 还具有 属性 可以一次完成处理的优点。如果你知道你要多次搜索相同的子字符串，你可以做一次 O(n) 预处理工作，然后能够在时间 O 中搜索你想要的任何长度为 m 的字符串(m).
我了解到KMP算法依赖于helper数组，其中有类似于后缀的前缀。 当不满足上述条件时，它不会有效，因为在辅助数组中包含全零。 运行时间会是 O(m + n) 吗？ 如果我是对的，在这种情况下更好的子串算法是什么？
要了解 KMP 何时是一个很好的算法，提出这个问题通常很有帮助 "what's the alternative?"
KMP 有一个很好的优势，它可以保证最坏情况下的效率。预处理时间总是 O(n)，搜索时间总是 O(m)。没有最坏情况的输入，没有倒霉的可能性等。如果您在非常大的字符串（大 m）中搜索非常长的字符串（大 n），与其他算法相比，这可能是非常可取的，例如朴素的（在糟糕的情况下可能需要时间 Θ(mn)）、Rabin-Karp（病态输入可能需要时间 Θ(mn)）或 Boyer-Moore（最坏的情况可能是 Θ(mn)）。你是对的，在字符串重叠部分不多的情况下，KMP 可能不是那么必要，但事实上你永远不需要担心是否有坏情况，这绝对是一件好事！
KMP 还具有 属性 可以一次完成处理的优点。如果你知道你要多次搜索相同的子字符串，你可以做一次 O(n) 预处理工作，然后能够在时间 O 中搜索你想要的任何长度为 m 的字符串(m).