什么时候可以使用KMP算法？

据我所知，KMP算法依赖于帮助程序数组，其中有前缀类似于后缀。当上述条件未满足时，它将无法有效，因为在帮助程序数组中包含全零。运行时会是O（m + n）吗？如果我是对的，在这种情况下什么是更好的子串算法？什么时候可以使用KMP算法？

2017-02-22 Jun

要理解KMP何时是一个很好的算法，通常可以提出问题“有什么选择？”。

KMP有一个很好的优势，它可以保证最差的效率。预处理时间总是O（n），搜索时间总是O（m）。没有最坏情况的输入，没有发生不幸的可能性等等。如果你在真正巨大的字符串（大m）内搜索非常长的字符串（大n），与其他算法相比，这可能是非常可取的天真的（在不好的情况下可能需要时间Θ（mn）），Rabin-Karp（病理输入可能需要时间Θ（mn））或Boyer-Moore（最坏情况可能是Θ（mn））。你说得对，KMP可能并不是所有必要的情况下，在字符串没有太多重叠部分的情况下，但是你永远不必担心是否存在不好的情况，这绝对是一件好事！

KMP还具有处理可以一次完成的好处。如果你知道你要搜索相同的子字符串很多次，你可以做一次O（n）预处理工作，然后有能力搜索任何长度为m的字符串，你想在时间O （M）。

来源

2017-03-01 22:52:28 templatetypedef

为什么会出现这种情况：没有最坏情况的输入，不可能发生不幸？当模式字符串中没有重复模式时，帮助程序数组将包含所有的零，这意味着，在字符串的每个字符处，我们必须返回到模式字符串的开头？ – Jun

@Jun回退数组将全部为零，并且在每次不匹配时，我们都必须返回到模式字符串的开头。但是，当发生这种情况时，我们还会在输入字符串中向前推进相应的距离。输入的每个字符最多只能被读取两次。 – templatetypedef

恩，我现在明白了！谢谢！ – Jun

什么时候可以使用KMP算法？

回答

相关问题