什么时候你会使用KMP而不是BOYER-MOORE

Question

我目前正在学习模式匹配算法，并遇到了这两种算法。我有以下大体的想法：

KMP

将文本与失败数组进行比较以移位字符串O(m)，其中m是模式的长度，以计算失败数组

• 花费O(m)，

• 花费O(n)，time to intelligently

• takes a

黑石

• 比较上一个代码中的模式坏字符跳转和好后缀跳转
• 需要O(m +字母表大小)来计算表
• 需要O(m +字母表大小)，空格
• 需要O(n)，但通常更好的搜索

<代码>F223

我遇到了下面的问题，它触发了这个问题(对或错)：

如果我们想要在许多不同的文本中重复搜索相同的模式，

算法是一个很好的选择。

所以我相信答案是正确的，因为假设每次你对不同的文本运行算法时，预处理只有O(n)，而对于BM，它是O(n +字母表的大小)。然而，我不确定我是否做了正确的假设，即每次重新运行算法时都会重新计算一个新表。因为说文本总是落在英语的字母表中。我只需要计算表一次，然后重用该表。那么，归根结底，这个问题的答案是否取决于算法都是在同一字母表中包含的文本上运行的事实，还是存在其他可能影响它的因素？

Answer 1

理论上，这两种算法的性能“相似”；KMP在搜索阶段将进行大约2n次比较，而Boyer-Moore在最坏情况下将在搜索阶段进行大约3n次比较。在这两种情况下，您都不需要在获得新文本时重复预处理。

但真正的答案是，您不应该在实践中使用这两种方法。

由于所有额外的内存访问，这两种算法所需的线性辅助存储导致了现代体系结构上的considerably...rougher性能。

然而，Boyer-Moore和KMP背后的思想支撑了大多数快速字符串匹配算法。我所知道的每个实际有效的字符串匹配算法都使用类似KMP的“失败函数”的思想；事实证明，您可以为一个模式即时计算一个次优的“失败函数”，它仍然提供线性时间匹配，而只需要恒定的额外空间。Boyer-Moore在匹配固定模式与随机噪声的“平均情况”中比线性更快，这在许多实际情况下都得到了证明。