algorithm - 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)是 m 位文本窗口的高位数字“1”的值。

这条线是什么意思？代表什么h？

Answer 1

您应该首先查看一个更简单的情况，其中dis10且文本仅包含 和 之间的0数字9。

h是您用于左移高位数字的值。例如，假设m是3和T = 2345。从234，您可以计算345如下：

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

在这种情况下，您可以看到h = 100用于2在减去 2 位之前移动 2 位数字234。请注意，h值为h = 103-1

现在，您可以将这个想法推广到 any d，并得到.h = dm-1

然后，通过进行模运算，您只需在mod q每次计算任何值时相加。