Python：Monte Carlo Rabin-Karp搜索

我正在嘗試在Python中實現蒙特卡羅Rabin-Karp搜索。這是我迄今爲止（random_prime就是比返回給定的極限arguement少一個素數的函數）：Python：Monte Carlo Rabin-Karp搜索

def search(pattern, text): 

m = len(pattern) 
n = len(text) 
q = random_prime(m*n*n) 
r = (2^(m - 1)) % q 
f = [] 
for x in range (0, n + 1): 
    f.append(0) 

pFinger = 0 
for j in range(0, m): 
    f[0] = (2 * f[0]) + (int(text[j]) % q) 
    pFinger = (2 * pFinger) + (int(pattern[j]) % q) 

i = 0 
while (i + m) < n: 
    if (f[i] == pFinger): 
     print "Match at position " + str(i) 
    f[i + 1] = (2 * (f[i] - (r * int(text[i])))) + (int(text[i + m]) % q) 
    i += 1

唯一的問題是，它似乎只匹配第一個字符或字符。

例如如果我打電話搜索（'01'，'101110001010101'），我找不到匹配。

或者如果我打電話搜索（'1'，'111110110100101'），我會得到一個匹配。

或者，如果我把搜索（「0」，「0000001110001010101」）我起牀匹配定位5.

有什麼不妥導致它無法正確匹配的代碼？

來源

2015-10-15 user_user

這是可以調試這個給你，但它不會幫助你多少。嘗試將打印輸出添加到您的代碼中。例如，在每次迭代中，打印出什麼是指紋。 –

我不是天才，但我想我找到了你的問題的根源。在行 r =（2 ^（m-1））％q，據我所知，^不是創建指數函數的正確字符。在python中使用的正確字符是**，使得r =（2 **（m-1））％q。您的搜索現在應該打印除最後一個以外的所有位置這然後可以通過= N在線改變< n至<（而第（i + M）<Ñ:)

您的代碼現在將打印所有的位置雖然將收到的索引差錯只發生一次全部被固定職位已經確定。這可以通過忽略這個錯誤一旦發生來解決。

嘗試：

f[i + 1] = (2 * (f[i] - (r * int(text[i])))) + (int(text[i + m]) % q) 

    i += 1

情況除外：

break

來源

2015-10-21 03:35:38 unknown

Python：Monte Carlo Rabin-Karp搜索

回答

相關問題