Rabin-Karp字符串匹配算法效率

Question

我知道Rabin字符串匹配算法是如何工作的，但是无法理解它如何比本地方法更好。在Rabin中，您可以为字符串中的每个子字符串找到散列，并将其与测试string.And的哈希值进行比较，如果匹配，则在本机方法中比较单个characters.However，您只需按字符将子字符串与测试字符串进行比较。没有必要计算散列，它如何比比较单个字符更快？

Answer 1

哈希比字符串短，可能只有一个字节。例如，如果您使用模251 ( 0-255范围内最高素数)进行比较，则如果比较字符串不同，则只进行单个字节比较99.6%。