algorithm - Knuth-Morris-Pratt 和 Boyer-Moore 搜索算法之间的主要区别是什么？

Question

Knuth-Morris-Pratt 搜索算法和 Boyer-Moore 搜索算法之间的主要区别是什么？

我知道 KMP 在 X 中搜索 Y，试图在 Y 中定义一个模式，并将该模式​​保存在一个向量中。我也知道 BM 更适合小词，例如 DNA (ACTG)。

它们工作方式的主要区别是什么？哪个更快？哪个对计算机不那么贪心？在哪些情况下？

Answer 1

Moore's UTexas webpage逐步介绍这两种算法(他还提供了各种技术资源):

• Knuth-Morris-Pratt
• Boyer-Moore

根据该男子本人的说法，

The classic Boyer-Moore algorithm suffers from the phenomenon that it tends not to work so efficiently on small alphabets like DNA. The skip distance tends to stop growing with the pattern length because substrings re-occur frequently. By remembering more of what has already been matched, one can get larger skips through the text. One can even arrange ``perfect memory'' and thus look at each character at most once, whereas the Boyer-Moore algorithm, while linear, may inspect a character from the text multiple times. This idea of remembering more has been explored in the literature by others. It suffers from the need for very large tables or state machines.

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