Rabin Karp 什么时候比 KMP 或 Boyer-Moore 更有效？
When is Rabin Karp more effective than KMP or Boyer-Moore?
我正在学习字符串搜索算法并了解它们的工作原理，但对于在哪些情况下 Rabin-Karp 算法比 KMP 或 Boyer-Moore 算法更有效，我还没有找到足够好的答案。我发现它更容易实现并且不需要相同的开销，但除此之外，我一无所知。
那么，什么时候使用 Rabin-Karp 比其他的更好？
这些算法中的每一个都具有一些属性，这些属性可能使它们在不同情况下令人满意或不受欢迎。这是一个快速 运行 向下：
Space使用优惠Rabin-Karp
Rabin-Karp 的一个主要优点是它使用 O(1) 辅助存储 space，如果您要查找的模式字符串非常大，这非常好。例如，如果您要在长度为 109 的较长字符串中查找所有出现的长度为 107 的字符串，则不必为故障函数分配一个 table of 107 个机器字，或者 shift table 是一个主要的胜利。 Boyer-Moore 和 KMP 都在长度为 n 的模式字符串上使用 Ω(n) 内存，因此 Rabin-Karp 在这里明显获胜。
Worst-Case Single-Match 效率优先 Boyer-Moore 或 KMP
Rabin-Karp 有两个潜在的最坏情况。首先，如果恶意对手知道 Rabin-Karp 使用的特定素数，那么该对手可能会制作一个输入，导致滚动哈希在每个时间点与模式字符串的哈希相匹配，从而导致算法的在长度为 m 的字符串和长度为 n 的模式上，性能会降低到 Ω((m - n + 1)n)。如果您将不受信任的字符串作为输入，这可能会成为一个问题。 Boyer-Moore 和 KMP 都没有这些弱点。
Worst-Case Multiple-Match效率有利于KMP。
类似地，如果您希望在某个模式字符串出现很多次的情况下找到该模式字符串的所有匹配项，则 Rabin-Karp 会很慢。例如，如果您在由 109 组成的文本字符串中查找字母 a 的 105 个副本的字符串字母 a 和 Rabin-Karp 的副本，然后会有很多点出现模式字符串，每个点都需要线性扫描。这也可能导致 运行 Ω((m + n - 1)n) 的时间。
许多 Boyer-Moore 实现都受到第二条规则的影响，但在第一种情况下不会有错误的 运行 次。而KMP没有这些病态的worst-cases
Best-Case性能优先Boyer-Moore
Boyer-Moore 算法的一个优点是它不必扫描输入字符串的所有字符。具体来说，错误字符规则可用于在不匹配的情况下跳过输入字符串的大量区域。更具体地说，Boyer-Moore 的 best-case 运行 时间是 O(m / n)，这比 Rabin-Karp 或 KMP 可以提供的要快得多。
对多个字符串的泛化有利于 KMP
假设您要搜索一组固定的多个文本字符串，而不仅仅是一个。如果愿意，您可以 运行 多次 Rabin-Karp、KMP 或 Boyer-Moore 遍历字符串以找到所有匹配项。但是，这种方法的 运行 时间并不长，因为它与要搜索的字符串数量成线性比例关系。另一方面，KMP 很好地概括了 Aho-Corasick string-matching 算法，该算法在时间 O(m + n + z) 中 运行s，其中 z 是找到的匹配数，n是模式字符串的组合长度。请注意，这里不依赖于要搜索的不同模式字符串的数量！
Rabin-Karp 算法在搜索寻找多个模式匹配的大文本时效果更好，例如检测抄袭。
和 Boyer-Moore 当模式相对较大、字母表大小适中且词汇量较大时效果更好。它不适用于二进制字符串或非常短的模式。
同时，KMP 适合在较小的字母表中搜索，例如在生物信息学中或在二进制字符串中搜索。如果字母表增加，它不会 运行 快。
Space-Time 三者的复杂度（供参考）
（用于查找所有出现的模式）
米：图案的长度
n：我们在其中搜索模式的字符串的长度
k : 字母表的大小
拉宾卡普:
O(1)辅助space
使用散列法查找文本中模式字符串的精确匹配。它使用滚动哈希快速过滤掉文本中不能匹配模式的位置，然后检查剩余位置的匹配
博耶摩尔：
Worst-case 性能：Θ(m) 预处理 + O(mn) 匹配
Best-case性能：Θ(m)预处理+Ω(n/m)匹配
Worst-case space 复杂度：Θ(k).
可用于“grep”之类的搜索。
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Performance
Knuth Morris Pratt:
Worst-case性能：Θ(m)预处理+Θ(n)匹配
Worst-case space 复杂度：Θ(m)
有关每个算法的更多详细信息，请在维基百科中查找。
我正在学习字符串搜索算法并了解它们的工作原理，但对于在哪些情况下 Rabin-Karp 算法比 KMP 或 Boyer-Moore 算法更有效，我还没有找到足够好的答案。我发现它更容易实现并且不需要相同的开销，但除此之外，我一无所知。
那么，什么时候使用 Rabin-Karp 比其他的更好？
这些算法中的每一个都具有一些属性，这些属性可能使它们在不同情况下令人满意或不受欢迎。这是一个快速 运行 向下：
Space使用优惠Rabin-Karp
Rabin-Karp 的一个主要优点是它使用 O(1) 辅助存储 space，如果您要查找的模式字符串非常大，这非常好。例如，如果您要在长度为 109 的较长字符串中查找所有出现的长度为 107 的字符串，则不必为故障函数分配一个 table of 107 个机器字，或者 shift table 是一个主要的胜利。 Boyer-Moore 和 KMP 都在长度为 n 的模式字符串上使用 Ω(n) 内存，因此 Rabin-Karp 在这里明显获胜。
Worst-Case Single-Match 效率优先 Boyer-Moore 或 KMP
Rabin-Karp 有两个潜在的最坏情况。首先，如果恶意对手知道 Rabin-Karp 使用的特定素数，那么该对手可能会制作一个输入，导致滚动哈希在每个时间点与模式字符串的哈希相匹配，从而导致算法的在长度为 m 的字符串和长度为 n 的模式上，性能会降低到 Ω((m - n + 1)n)。如果您将不受信任的字符串作为输入，这可能会成为一个问题。 Boyer-Moore 和 KMP 都没有这些弱点。
Worst-Case Multiple-Match效率有利于KMP。
类似地，如果您希望在某个模式字符串出现很多次的情况下找到该模式字符串的所有匹配项，则 Rabin-Karp 会很慢。例如，如果您在由 109 组成的文本字符串中查找字母 a 的 105 个副本的字符串字母 a 和 Rabin-Karp 的副本，然后会有很多点出现模式字符串，每个点都需要线性扫描。这也可能导致 运行 Ω((m + n - 1)n) 的时间。
许多 Boyer-Moore 实现都受到第二条规则的影响，但在第一种情况下不会有错误的 运行 次。而KMP没有这些病态的worst-cases
Best-Case性能优先Boyer-Moore
Boyer-Moore 算法的一个优点是它不必扫描输入字符串的所有字符。具体来说，错误字符规则可用于在不匹配的情况下跳过输入字符串的大量区域。更具体地说，Boyer-Moore 的 best-case 运行 时间是 O(m / n)，这比 Rabin-Karp 或 KMP 可以提供的要快得多。
对多个字符串的泛化有利于 KMP
假设您要搜索一组固定的多个文本字符串，而不仅仅是一个。如果愿意，您可以 运行 多次 Rabin-Karp、KMP 或 Boyer-Moore 遍历字符串以找到所有匹配项。但是，这种方法的 运行 时间并不长，因为它与要搜索的字符串数量成线性比例关系。另一方面，KMP 很好地概括了 Aho-Corasick string-matching 算法，该算法在时间 O(m + n + z) 中 运行s，其中 z 是找到的匹配数，n是模式字符串的组合长度。请注意，这里不依赖于要搜索的不同模式字符串的数量！
Rabin-Karp 算法在搜索寻找多个模式匹配的大文本时效果更好，例如检测抄袭。
和 Boyer-Moore 当模式相对较大、字母表大小适中且词汇量较大时效果更好。它不适用于二进制字符串或非常短的模式。
同时，KMP 适合在较小的字母表中搜索，例如在生物信息学中或在二进制字符串中搜索。如果字母表增加，它不会 运行 快。
Space-Time 三者的复杂度（供参考） （用于查找所有出现的模式）
米：图案的长度
n：我们在其中搜索模式的字符串的长度
k : 字母表的大小
拉宾卡普:
O(1)辅助space
使用散列法查找文本中模式字符串的精确匹配。它使用滚动哈希快速过滤掉文本中不能匹配模式的位置，然后检查剩余位置的匹配
博耶摩尔：
Worst-case 性能：Θ(m) 预处理 + O(mn) 匹配
Best-case性能：Θ(m)预处理+Ω(n/m)匹配
Worst-case space 复杂度：Θ(k).
可用于“grep”之类的搜索。 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Performance
Knuth Morris Pratt:
Worst-case性能：Θ(m)预处理+Θ(n)匹配
Worst-case space 复杂度：Θ(m)
有关每个算法的更多详细信息，请在维基百科中查找。