Python: алгоритм алгоритма Рабина-Карпа

Question

Я реализую алгоритм Рабина-Карпа для удовольствия. Я наткнулся на этот псевдокод:

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 

где результат список, содержащий индекс в тексте шаблона.

Мой код не находит 26 в 3141592653589793 , и я подозреваю, что он имеет какое-то отношение к моему хэш-коду, определенному строкой 14 псевдокода. Кто-нибудь может помочь с этим.

я проходил в следующих paramters:

P = "26" Т = "3141592653589793" д = 257 д = 11

Р и Т должны быть строками/массивов символов

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). Проверено на втором примере (поиск «xx» в «xxxxx»).

Также стоит отметить:

1. Линия h = pow(d,m-1)%q может быть слишком медленным, если m велико. Лучше взять результат по модулю q после каждого из умножений m-2.

2. Этот алгоритм все еще O (нм) в худшем случае. С text="a"*100000 и pattern="a"*50000 он найдет 50001 позиций, где подстрока текста соответствует шаблону, и он будет проверять их все по-символам. Если вы ожидаете, что ваш код будет работать быстро в таких крайних случаях, вы должны пропустить сравнение по каждому символу и найти способ справиться с ложными срабатываниями (т., хэши равны, но строк нет). Выбор большого простого числа q может помочь уменьшить вероятность ложного срабатывания до приемлемого уровня.

Answer 2

Итак, ответ в том, что вам нужно отступ «для s» цикла:

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, и это то, что вы ищете, я себе представляю. Интересный алгоритм.