Cormen字符串匹配拉宾，卡普

Question

我读拉宾，卡普算法通过算法导论由Cormen等

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

注意这里==作为MOD操作

上方幻灯片备注13即公式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值模q的行为就像从sigma *到Z的随机映射的假设基础启发式分析。

Answer 1

你的第二个问题似乎只是关于-ve数字的模运算。一种想法是，工作模式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对散列值的影响。