这是您的代码的有效版本：
def Rabin_Karp_Matcher(text, pattern, d, q): n = len(text) m = len(pattern) h = pow(d,m-1)%q p = 0 t = 0 result = [] for i in range(m): # preprocessing p = (d*p+ord(pattern[i]))%q t = (d*t+ord(text[i]))%q for s in range(n-m+1): # note the +1 if p == t: # check character by character match = True for i in range(m): if pattern[i] != text[s+i]: match = False break if match: result = result + [s] if s < n-m: t = (t-h*ord(text[s]))%q # remove letter s t = (t*d+ord(text[s+m]))%q # add letter s+m t = (t+q)%q # make sure that t >= 0 return resultprint (Rabin_Karp_Matcher ("3141592653589793", "26", 257, 11))print (Rabin_Karp_Matcher ("xxxxx", "xx", 40999999, 999999937))输出为：
[6][0, 1, 2, 3]
第一步，检查是否
text[0..m] == pattern。在第二步中，您要检查是否
text[1..m+1] ==pattern。因此，您删除
text[0]从哈希（目前它是由您的预计算乘
h）
t =(t-h*ord(text[s]))%q。然后添加
text[m]到：
t =(t*d+ord(text[s+m]))%q。在下一步中，删除
text[1]并添加
text[m+1]，依此类推。出现这
t =(t+q)%q条线是因为模数的负数
q产生的余数在该范围内
(-q; 0]，我们希望它在该范围内
[0; q)。
请注意，您不希望检查
n-m+1子字符串总数
n-m，因此正确的循环是
for s in range(n-m+1)。由第二个示例检查（在“
xxxxx”中找到“ xx”）。
另外值得注意的是：
h = pow(d,m-1)%q
如果太大，线可能太慢m
。最好q
在每个m-2
乘法之后对结果取模。在最坏的情况下，该算法仍为O（nm）。使用
text="a"*100000
和pattern="a"*50000
，它将找到50001个文本子字符串与模式匹配的位置，并将逐个字符地检查它们。如果您希望代码在这样的极端情况下可以快速运行，则应跳过逐个字符的比较，并找到一种处理误报的方法（即，哈希值相等而字符串不相等）。选择大质数q
可能有助于将误报的可能性降低到可接受的水平。
