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。