algorithm - 在 RabinKarp 算法中，为什么要先比较哈希？

Question

在 Rabin Karp 子串搜索算法中：

1) 计算子串的哈希值 2) 取一个滑动窗口[等于子串的大小]，并将窗口中存在的字符串的哈希值与子串的哈希值进行比较。3）如果哈希匹配，那么我们将窗口内容与子字符串进行比较。

问题： 1）首先匹配哈希而不是比较在性能方面有什么好处？为什么我们不能只是比较？比较哈希可以更快但如何（我没有得到）？

Answer 1

O(1)随着窗口的滑动，计算新的哈希值和O(1)比较哈希值只需要时间。

O(m)每次滑动窗口时进行完整的字符串比较都需要花费时间，其中m是子字符串的长度，并且可能会遭受分支错误预测的影响。