Rabin-Carp字符串匹配算法的效率

Question

我知道Rabin Karp字符串匹配算法是如何工作的，但无法理解它如何比原生方法更好。在RabinKarp中，您可以找到字符串中每个子字符串的散列，并将其与测试字符串的散列值进行比较。如果匹配，现在可以比较各个字符。然而，在本机方法中，您只需逐个字符地将子字符串和测试字符串进行比较。计算哈希不是没有必要的吗？它怎么比比较单个字符更快？

Answer 1

散列比字符串短，可能只有一个字节。例如，如果您通过模251(0-255范围内的最高素数(进行比较，那么如果比较的字符串不同，则只有99.6%的时间进行单字节比较。