Python：Rabin

Python：Rabin

这是您的代码的有效版本：

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”）。

另外值得注意的是：

1. h = pow(d,m-1)%q

   如果太大，线可能太慢

   m

   。最好

   q

   在每个

   m-2

   乘法之后对结果取模。

2. 在最坏的情况下，该算法仍为O（nm）。使用

   text="a"*100000

   和

   pattern="a"*50000

   ，它将找到50001个文本子字符串与模式匹配的位置，并将逐个字符地检查它们。如果您希望代码在这样的极端情况下可以快速运行，则应跳过逐个字符的比较，并找到一种处理误报的方法（即，哈希值相等而字符串不相等）。选择大质数

   q

   可能有助于将误报的可能性降低到可接受的水平。