我正在阅读 Cormen 的算法简介等的 Rabin-Karp 算法。
www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt
注意这里 == 用作 mod 运算符
以上幻灯片 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 的随机映射。这里作者的上述陈述是什么意思？
您的第二个问题似乎只是关于带有 -ve 数字的模运算。考虑这一点的一种方法是，工作 mod M 您可以随意添加或减去 M，因为 M 等于 0 mod M。所以我们有 (7-3.3).10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 mod 13
你的第一个问题对我来说不太清楚，但让我详细解释一下。当一个字符第一次出现在文本窗口中时，它只是被添加进来。然后它沿着文本窗口移动，最后我们要删除它的所有内存，这样它移出文本窗口后就不会影响哈希值。
首先我们看到字符 x，并将它添加到到目前为止的哈希值中，所以我们得到 hd + x。当我们看到下一个字符时，我们将它乘以 d（并做我试图解释的其他事情），然后添加新字符 - 说 y。所以我们得到... + x*d + y。下一步给我们... + x*d*d + y*d + z。当我们即将删除字符时，我们有一个哈希值 x*d^(m-1) + ....，其中 .... 仅取决于 x 之后的字符。所以我们可以通过在乘以 d 之前减去 x*d^(m-1) 来消除 x 对哈希值的影响。