algorithm - 无法理解 topcoder 解释的 Rabin Karp 算法的哈希函数

Question

我在 Topcoder 阅读 Rabin Karp 算法。但是在那篇文章中，我无法获得以下哈希评估。

  // calculate the hash value of the first segment 
  // of the text of length m
  ht = 0;
  for(i = 0; i < m; i++) 
    ht = int_mod(ht * B + text[i], M);

它看起来与理论中解释的不同。我知道我可以自由地使用 Rabin Karp 中的任何哈希函数，但仍然要保持教程的流程，我需要解释一下，因为我可能没有正确理解它。

Answer 1

对我来说，它看起来与之前的理论相同。诀窍是他们分小步进行（构造多项式）

考虑一个长度为 3 的字符串的非常简单的示例：

我们初始化ht = 0. 循环将首先获得位置 0: ht = text[0] 现在，对于位置 1，我们获得B: 的第一个幂ht = text[0]*B + text[1]。在第三次迭代中，我们通过再次乘以B整个“多项式”来获得二次幂：ht = text[0]*B^2 + text[1]*B + text[2]. 当然，我们可以M在每一步都做模数。

这正是文章中上面的哈希值。