string - Cormen 字符串匹配 Rabin-Karp

Question

我正在阅读 Cormen 等人的算法导论中的 Rabin-Karp 算法。

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

注意这里==用作模运算符

幻灯片 13 上的注释，即 Eq 34.2，作为图片附在此处。在等式中，我们有 h == (d)powerof((m-1) (mod q) 是 m 位文本窗口高位位置的数字“1”的值。

我的问题是作者所说的“m 位文本窗口高位数字“1”的值”是什么意思？

在幻灯片 14 中，作者如何将 (7-3.3).10 + 2 (mod 13) 变为 8 (mod 13)？

在平均案例分析中提到，我们可以基于这样的假设进行启发式分析:以 q 为模减少值就像从 sigma* 到 Z 的随机映射。作者在上面的陈述中是什么意思？

Answer 1

您的第二个问题似乎只是关于具有 -ve 个数的模运算。一种思考方式是，使用 mod M 时，您可以随意添加或减去 M，因为 M 等于 0 mod M。所以我们有 (7-3.3).10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 模 13

我不太清楚你的第一个问题，但让我详细解决一下。当一个字符第一次出现在文本窗口中时，它只是被添加进来。然后它沿着文本窗口移动，最后我们要删除它的所有内存，这样它移出文本窗口后不影响哈希值。

首先我们看到字符x，将它加到到目前为止的哈希值中，所以我们得到h.d + x。当我们看到下一个字符时，我们将其乘以 d(并执行我试图解释的其他操作)，然后添加新字符 - 说 y。所以我们得到 ... + x*d + y。下一步给我们 ... + x*d*d + y*d + z。当我们正要摆脱字符时，我们有一个散列值 x*d^(m-1) + ....，其中 .... 仅取决于 x 之后的字符。所以我们可以通过在乘以d之前减去x*d^(m-1)来去除x对哈希值的影响。