问Knuth Pratt和Boyer搜索算法的主要区别是什么？

EN

Moore's UTexas webpage一步一步地介绍了这两种算法(他还提供了各种技术来源)：

• Knuth-Morris-Pratt
• Boyer-Moore

据他自己说，

经典的Boyer算法存在这样一种现象，即它在诸如DNA这样的小字母上不那么有效地工作。跳过距离往往会随着模式长度的增加而停止增长，因为子字符串经常重复发生。通过记住更多已经匹配的内容，人们可以在文本中得到更大的跳过。人们甚至可以排列完美记忆‘’，因此最多只能查看每个字符，而Boyer算法虽然是线性的，但可能会从文本中多次检查字符。这种记忆更多的想法已经在文献中被其他人探索过了。它需要非常大的表或状态机。

然而，也有一些modifications of BM使得小字母表搜索变得可行。

用粗略的解释

Boyer-Moore的方法是尝试匹配模式的最后一个字符，而不是第一个字符，假设如果最后没有匹配，就不需要在开始时尝试匹配。这允许“大跳跃”，因此，当您正在搜索的模式和文本类似于“自然文本”(即英语)时，BM工作得更好。

Knuth-Morris-Pratt搜索主“文本字符串”S中出现的“单词”W，方法是使用这样的观察:当发生不匹配时，单词本身包含足够的信息来确定下一次匹配可以从何处开始，从而绕过对先前匹配字符的重新检查。(资料来源：Wiki)

这意味着KMP更适合像DNA这样的小集集。

Boyer技术从右到左匹配字符，在长模式上工作良好.knuth moris pratt从左到右匹配字符，在短模式上快速工作。