科尔曼字符串匹配Rabin-Karp

Question

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

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

注意这里使用==作为mod运算符

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

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

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

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

Answer 1

你的第二个问题似乎只是关于-ve数的模算术。考虑这个问题的一种方法是，你可以随意增加或减少M，因为M等于0mod M。所以我们有(7-3.3).10 +2 (mod 13) = -2.10 +2= -18 = 13 + 13 - 18 =8 mod 13

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

首先，我们看到字符x，并将其添加到到目前为止的散列值中，因此我们得到h.d +x。当我们看到下一个字符时，我们将其乘以d(并执行我试图解释的其他事情)，然后添加新字符-例如y。因此，我们得到... + x*d + y。下一步是... + x*d*d + y*d + z。当我们要删除该字符时，我们的散列值为x*d^(m-1) + ....，其中...因此我们可以通过在乘以d之前减去x*d^(m-1)来消除x对散列值的影响。