Python: хеширование алгоритма Рабина-карпа

Вот рабочая версия вашего кода:

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 (nm) в худшем случае. С помощью text="a"*100000 и pattern="a"*50000 он найдет 50001 позицию, в которой подстрока текста соответствует шаблону, и проверит их все по символам. Если вы ожидаете, что ваш код будет работать быстро в таких экстремальных случаях, вы должны пропустить сравнение символов и найти способ справиться с ложными срабатываниями (т. е. хэши равны, а строки-нет). Выбор большого простого числа q может помочь снизить вероятность ложного срабатывания до приемлемого уровня.