algorithm - Knuth Morris Pratt vs Boyer Moore : binary alphabet vs alphabet with large number of letters

Question

我熟悉这两种算法:Knuth Morris Pratt 和 Boyer moore。

给定一个由大量字母组成的字符串 P。哪种算法更好用？

给定一个带有二进制字母表(0 或 1)的字符串 P。哪种算法更好用？

Answer 1

Boyer-Moore 相对于 KMP 的主要优势在于 Boyer-Moore 可以具有亚线性运行时间。但是，当您要查找的模式中没有很多不匹配字符时会发生这种情况(因为这允许算法在文本中跳得更远)。在大型字母表中，模式外的字符更可能不匹配，因此 Boyer-Moore 可能是那里的最佳选择。但是请记住，在最坏的情况下，BM 在 ~MN 中运行，其中 M 是模式的大小，N 是文本的大小，而 KMP 保证是线性的。

对于二进制字母表，我会选择 KMP。 BM 中的不匹配字符几乎总是在模式中，因此您可能会线性地处理文本，在这种情况下，两种算法之间几乎没有区别。但是，二进制字母表中的 BM 更容易命中最坏情况，因此 KMP 更安全。