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對散列值的影響。