我为了好玩而实现 Rabin-Karp 算法。我遇到了这个伪代码:
RABIN -KARP -MATCHER (T, P, d, q)
1 n = T.length
2 m = P.length
3 h = d^(m-1) mod q
4 p=0
5 t= 0
6 for i = 1 to m
/ preprocessing
/
7 p = (dp + P [i]) mod q
8 t = (dt + T [i]) mod q
9 for s = 0 to n-m
/ matching
/
10 if p == t
11 if P [1... m] == T [s + 1...s + m]
12 print “Pattern occurs with shift” s
13 if s < n-m
14 t = (d(t-T[s + 1]h) + T [s + m + 1]) mod q
我在 Python 2.7 中实现如下:
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):
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 = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here
return result
其中结果是包含模式文本中的索引的列表。
我的代码无法在 3141592653589793 中找到 26
我怀疑这与伪代码第 14 行定义的哈希码有关。任何人都可以帮忙解决这个问题吗?
我传入了以下参数:
P =“26”
T =“3141592653589793”
d = 257
q = 11
P 和 T 必须是字符串/字符数组
这是您的代码的工作版本:
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 result
print (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]
to it: 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
乘法。或者直接使用内置的方式:h = pow(d,m-1,q)
,正如@oBrstisf8o 在评论中所建议的。
-
该算法在最坏情况下仍然是O(nm)。和text="a"*100000
and pattern="a"*50000
,它会找到 50001 个文本子字符串与模式匹配的位置,并且会逐个字符地检查它们。如果您希望代码在这种极端情况下能够快速运行,则应该跳过逐个字符的比较,并找到一种处理误报的方法(即哈希值相等但字符串不相等)。选择一个大素数q
可能有助于将误报的可能性降低到可接受的水平。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)