Путаница в отношении скользящего хэша в алгоритме Рабина-Карпа Java

Question

Я пытался понять алгоритм Рабина-Карпа здесь: http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html.

Я просмотрел различные статьи и теперь я знаю, что общая форма полиномиального хэша: C1*A^k-1+C2*A^k-2+C3*A^k-3. Глядя на код, я понимаю, как они складывают и вычитают цифры в строке.

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; txtHash = (txtHash*R + txt.charAt(i)) % Q;

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

 private long hash(String key, int M) { 
    long h = 0; 
    for (int j = 0; j < M; j++) 
        h = (R * h + key.charAt(j)) % Q; 
    return h; 
} 

В этой функции они умножают хеш и основание, а затем добавляют key.charAt(). Я бы подумал, что функция будет умножать key.charAt () с базой, которая начинается в R^k-1. Затем, когда цикл for продолжается, основание делится на R, чтобы обеспечить уменьшение мощности в полиноме. Может кто-нибудь объяснить, как работает эта функция и как она генерирует хэш в форме, которую я упоминал выше? Спасибо!

Answer 1

Предположим, что хэш-функция должна передавать 3 цифры. Это будет выглядеть так:

{digits[0]*R^2+digits[1]*R^1+digits[2]}%Q  
= {(digit[0]*R^1+digits[1])*R+digits[2]}%Q  

Это облегчит вычисление хеш-функции.

Затем примените к алгоритму Рабина-Карпа,
ты можешь видеть

RM = R^2 %Q;(M=2) 

когда вы хотите переместить следующую цифру для подтверждения,
вам нужно удалить самую левую цифру и добавить следующую цифру.

txtHash = {[txtHash - R^2*most_left_digit(equal charAt(i-M))]*R+next_digit(equal charAt(i))}%Q  

Это так же, как

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q; 
txtHash = (txtHash*R + txt.charAt(i)) % Q;

Мод Q каждый шаг предотвращает переполнение.