我正在学习字符串搜索算法并了解它们的工作原理，但还没有找到足够好的答案来说明在哪些情况下 Rabin-Karp 算法比 KMP 或 Boyer-Moore 更有效。我看到它更容易实现并且不需要相同的开销，但除此之外，我不知道。
那么，Rabin-Karp 什么时候比其他人更好用呢？
最佳答案
这些算法中的每一个都具有一些属性，可能会使它们在不同的情况下变得可取或不可取。这是一个快速概述:
空间利用有利于拉宾-卡普
Rabin-Karp 的一大优势是它使用 O(1) 辅助存储空间，如果您要查找的模式字符串非常大，这非常有用。例如，如果您要在长度为 109 的较长字符串中查找所有出现的长度为 107 的字符串，那么不必为故障函数或移位表分配一个包含 107 个机器字的表是一个重大胜利。 Boyer-Moore 和 KMP 都在长度为 n 的模式字符串上使用 Ω(n) 内存，因此 Rabin-Karp 在这里显然是赢家。
最坏情况的单场比赛效率有利于 Boyer-Moore 或 KMP
Rabin-Karp 面临两种潜在的最坏情况。首先，如果恶意对手知道 Rabin-Karp 使用的特定素数，则该对手可能会制作一个输入，导致滚动哈希在每个时间点与模式字符串的哈希匹配，从而导致算法的性能下降在长度为 m 的字符串和长度为 n 的模式上降级为 Ω((m - n + 1)n)。如果您将不受信任的字符串作为输入，这可能是一个问题。 Boyer-Moore 和 KMP 都没有这些弱点。
最坏情况多匹配效率有利于 KMP。
类似地，Rabin-Karp 在您想在该模式出现大量次数的情况下找到该模式字符串的所有匹配项的情况下很慢。例如，如果您要查找字母 a 的 105 个副本的字符串。在由 109 个字母 a 组成的文本字符串中使用 Rabin-Karp，那么在模式串出现的地方会有很多点，每个点都需要线性扫描。这也可能导致 Ω((m + n - 1)n) 的运行时间。
许多 Boyer-Moore 实现都受第二条规则的影响，但在第一种情况下不会有糟糕的运行时。 KMP 没有像这样的病理学最坏情况。
最佳情况下的表现有利于 Boyer-Moore
Boyer-Moore 算法的优点之一是它不必扫描输入字符串的所有字符。具体来说，坏字符规则可用于在不匹配的情况下跳过输入字符串的巨大区域。更具体地说，Boyer-Moore 的最佳运行时间是 O(m/n)，这比 Rabin-Karp 或 KMP 所能提供的要快得多。
对多个字符串的概括有利于 KMP
假设您有一组固定的要搜索的多个文本字符串，而不仅仅是一个。如果您愿意，您可以在字符串上多次运行 Rabin-Karp、KMP 或 Boyer-Moore 以查找所有匹配项。然而，这种方法的运行时间并不好，因为它与要搜索的字符串数量呈线性关系。另一方面，KMP 很好地推广到 Aho-Corasick 字符串匹配算法，该算法在 O(m + n + z) 时间内运行，其中 z 是找到的匹配数，n 是模式字符串的组合长度。请注意，这里不依赖于正在搜索的不同模式字符串的数量!
关于string-search - Rabin Karp 什么时候比 KMP 或 Boyer-Moore 更有效？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56418773/