rabin karp算法中「h」代表什麼？

Question

t(s+1) = (d*(t(s) -T[s+1]h) + T[s+m+1])mod q 

d是字母表
T[1...n]的尺寸要搜索
P[1...m]是圖案（m是圖案的尺寸）
q文本是一個素數

h = d^m-1 (mod q)是值數字「1」在m位文本窗口的高位位置。

這條線是什麼意思？ h代表什麼？

Answer 1

您應該首先看一個更簡單的情況，其中d是10，文本只包含0和9之間的數字。

h是你使用的值左移的高位數字。例如，我們假設m是3和T = 2345。

345 = 10*(234 - 2*100) + 5 

您可以在此情況下h = 100看到的是用於從234減去之前移動由2位數字2：從234，您可以按以下方法計算345。請注意，h的值爲h = 103-1

現在，您可以概括任何d的想法，並獲得h = dm-1。

然後，通過模操作，每次計算任何值時只需添加mod q。