Python: Monte Carlo Rabin-Karp search

Question

Я пытаюсь реализовать поиск в Карте Рабина-Карпа в Python. Это то, что я до сих пор (random_prime это функция, которая возвращает простое число меньше предельного arguement заданного):

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.

Есть ли что-то не так с кодом, который вызывает его, чтобы соответствовать неправильно?

Answer 1

Я не гений, но я думаю, что нашел корень вашей проблемы. В строке r = (2^(m - 1))% q, насколько я знаю,^не является правильным символом для создания экспоненциальной функции. Правильный символ для использования в python был бы таким, что r = (2 ** (m - 1))% q. Теперь ваш поиск должен печатать все позиции, кроме последнего. Это может затем быть исправлено путем изменения < < п к = п в строке (в то время как (я + т) < п :)

Вы код теперь будет печатать все позиции, хотя вы получите сообщение об ошибке индекса, который происходит только один раз все были определены позиции. Это можно решить, проигнорировав эту ошибку после ее возникновения.

попробовать:

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

    i += 1 

кроме:

break