algorithm - Knuth Morris Pratt vs Boyer Moore : 二进制字母 vs 带有大量字母的字母

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 更安全。