Cormen 字符串匹配 Rabin-Karp
我正在阅读 Cormen 等人的《算法简介》中的 Rabin-Karp 算法
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) as 8 (mod 13)？
在平均情况分析中据说我们可以基于以下假设进行启发式分析：以 q 为模减少值就像从 sigma* 到 Z 的随机映射。作者上述陈述的意思是什么？
I am reading Rabin-Karp algorithm by Introduction to Algorithms by Cormen etc.
www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt
Note here == is used as mod operator
Above notes on slide 13 i.e., Eq 34.2, which is attached as picture here. In equation we have h == (d)powerof((m-1) (mod q) is value of digit "1" in the high order position of an m-digit text window.
My question here what does author mean by "value of digit "1" in the high order position of an m-digit text window" ?
On slide 14 how author got (7-3.3).10 + 2 (mod 13) as 8 (mod 13)?
In Average case analysis it is mentioned that we can base a heuristic analysis on the assumption that reducing values modulo q acts like a random mapping from sigma* to Z. Here what does author mean by above statement?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你的第二个问题似乎只是关于带有 -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对哈希值的影响。
Your second question seems just to be about modular arithmetic with -ve numbers. One way to think of this is that working mod M you are free to add or subtract M as much as you like, since M is equivalent to 0 mod M. So we have (7-3.3).10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 mod 13
Your first question is less clear to me, but let me work through it in detail. When a character first appears in the text window, it is just added in. Then it shifts along the text window, and finally we want to remove all memory of it, so that after it moves out of the text window it does not affect the hash value.
At first we see character x, and add it to the hash value so far, so we get h.d + x. When we see the next character we multiply that by d (and do the other stuff I am trying to explain) and then add on the new character - say y. So we get ... + x*d + y. The next step gives us ... + x*d*d + y*d + z. When we are just about to get rid of the character we have a hash value of x*d^(m-1) + ...., where .... depends only on characters after x. So we can remove the influence of x on the hash value by subtracting x*d^(m-1) before multiplying by d.