我目前正在学习模式匹配算法，并遇到了这两种算法。我的总体思路如下:
公里
- 从左到右比较文本
- 使用故障数组智能移位
- 计算故障数组 需要O(m)，其中m为模式的长度。
- 占用0 (m)，空格
- 搜索字符串 耗时O(n)
BM
- 比较最后一个字符 的模式
- 使用坏字符跳转和好的后缀跳转
- 需要O(m +字母大小)来计算表
- 占用0 (m +字母大小)，空格
- 耗时O(n)，但通常最好搜索
我遇到了下面的问题，触发了这个问题(对还是错):
如果我们想要，Knuth-Morris-Pratt (KMP)算法是一个很好的选择在许多不同的文本中重复搜索相同的模式。
所以我相信答案是正确的，因为假设每次你在不同的文本上运行算法，预处理只有O(n)，而对于BM，它是O(n +字母表的大小)。但是，我不确定我是否做出了正确的假设，即每次重新运行算法时都会重新计算一个新表。因为说文本总是落在英语的字母表里。我只需要计算这个表一次，然后重用这个表。所以在一天结束的时候，这个问题的答案是否取决于算法都是在包含在相同字母表中的文本上运行的这个事实，或者是否有其他因素可能会影响它?
理论上，两种算法将具有"相似"的性能;KMP将在搜索阶段进行大约2n次比较，在最坏的情况下，Boyer-Moore将在搜索阶段进行大约3n次比较。在这两种情况下，当你得到一个新的文本时，你都不需要重复预处理。
但真正的答案是你不应该在实践中使用这两种方法。
两种算法所需的线性辅助存储导致相当…由于所有额外的内存访问，在现代架构上性能更差。
然而，Boyer-Moore和KMP背后的思想是大多数快速字符串匹配算法的基础。像KMP的"失败函数"这样的想法被我所知道的每一个实际有效的字符串匹配算法所使用;事实证明，您可以为动态模式计算一个次优的"失败函数"，它仍然为您提供线性时间匹配，同时只需要恒定的额外空间。在匹配固定模式与随机噪声的"平均情况"下，Boyer-Moore比线性更快，这在许多实际情况下都得到了证明。一个老帖子，我知道，但我不能让它…如果你追求速度，永远不要使用任何形式的KMP。它的优点是无论输入是什么，它的时间都是一致的，但与其他算法相比，它总是很慢。它具有重要的历史意义，而且作为教学辅助工具很有用，但除此之外……不。看看这里，试着决定哪个算法符合你的用例https://arxiv.org/pdf/1012.2547v1.pdf如果做不到，BM或BMH可能是你最好的。