问Knuth Morris Pratt vs Boyer Moore :二进制字母表与大量字母的字母表

EN

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

对于二进制字母表，我会使用KMP。BM中的不匹配字符几乎总是在模式中，因此您可能会线性地处理整个文本，在这种情况下，两种算法之间几乎没有区别。然而，对于二进制字母表中的BM来说，遇到最坏的情况要容易得多，所以KMP更安全。