Python：Rabin-Karp算法哈希

Question

我正在實現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必須是字符串/數組：

我在以下paramters傳遞

Answer 1

這裏是你的代碼的工作版本：

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]：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. 線​​可能是，如果m大太慢。在每個m-2乘法之後，最好取模q。

2. 該算法在最壞的情況下仍然是O（nm）。使用text="a"*100000和pattern="a"*50000，它會找到50001個位置，其中文本的子字符串與該模式相匹配，並且它將逐字符地檢查它們。如果您希望代碼在極端情況下快速運行，您應該跳過逐字符比較並找出處理誤報的方法。，哈希是平等的，但字符串不是）。挑選大質數q可能有助於將誤報的可能性降低到可接受的水平。

Answer 2

好了，答案是，你需要縮進了「的」循環：

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 

這給了我一個在nswer 6，這正是你想要的我想象的。有趣的算法人。