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

Question

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

  // 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 乘以整个 'polynomial' 得到二次方：ht = text[0]*B^2 + text[1]*B + text[2]。当然，我们可以在每一步都取模 M。

这正是文章上面的散列。

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

Unable to understand the hash function of Rabin Karp Algorithm explained at topcoder

algorithm

hash

rabin-karp