java RabinKarp算法：为什么h=（h*d）%q

Question

我理解拉宾-卡普算法中的以下内容

h=d^m-1但我不明白我们为什么要写

for(i=0;i<M-1;i++)
    h=(h*d)%q

在代码中

Answer 1

基本上，这些行将默认值初始化到hashmaps中，稍后您将对其进行更改，它还可以作为一个哈希函数使用，当您插入值时，为了更深入的了解，请阅读paragragh下面的内容，还可以投票并遵循我的个人资料。 当你们试图理解hashmaps的概念时，每个人都会通过串联一些块来教你们。后来，这些块初始化了一些键值，但在插入键值之前，该块未初始化。因此，有些块可能没有被赋予任何键值。它们将包含垃圾值，您如何遍历它们，因为当您需要搜索某个内容时，您需要遍历，所以该函数正在初始化所有块的默认值。现在，如果您尝试在没有这些行的情况下运行代码，您的代码将只进行第一次检查。据我所知，这些代码行来自Geeksforgeks-rabinkarp算法，尝试在没有这些代码行的情况下运行代码，您将只检查第一个值，而不会得到所需的答案

Answer 2

准确地说，循环不是在计算ℎ=𝑑^𝑚−1，但ℎ=(𝑑^𝑚−1） 国防部𝑞。这是一个重要的细节，因为这意味着𝑑 或𝑚 是的，结果永远不会超过𝑞.

此外，您展示的代码块前面需要加上h=1才能有意义

通过循环，我们可以避免大的中间结果，这可能会超出所使用的整数类型支持的范围。通常是字符串字母表的大小(𝑑) 设置为256。现在如果要搜索的图案的长度(𝑚) 大概是20岁吧𝑑^𝑚=256²⁰=2¹⁶⁰，这个数字不适合典型的32位或64位整数存储。算计𝑑^𝑚−1就像那样，可能会导致数字溢出

这就是为什么使用循环。在每次迭代中，都会应用模运算符，其正常值为𝑑 和𝑚 消除了溢出的风险。在每次迭代中应用模算子也是非常困难的