Рабин-Карп: скользящее вычисление хеша добавляет большое простое число к ранее вычисленному хешу

Question

Я думаю, что концептуально понимаю алгоритм сопоставления с шаблоном RabinKarp с использованием скользящего хэша.Проходя пример реализации здесь , я обнаружил, что к ранее вычисленному скользящему хешу добавлено большое простое число q.

for (int i = m; i < n; i++) {
            // Remove leading digit, add trailing digit, check for match. 
            txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q; //Why +q here?
            txtHash = (txtHash*R + txt.charAt(i)) % q; 

            // match
            int offset = i - m + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }

Я не уверен, зачем это нужно,Могу ли я получить помощь с этим?

В моем ограниченном тестировании я получаю один и тот же результат, независимо от того, включен ли q термин.

Имеет ли это какое-то отношение к какой версии алгоритма (Монте-Карло / Лас-Вегас)внедряется?

Answer 1

Термин +q используется для того, чтобы избежать отрицательных чисел.

Мы хотим, чтобы txtHash всегда лежал в интервале [0;q[, без этого +q он также может быть в ]q;0[.

Это может привести к отсутствию шаблона. например, если patHash = 0xdead, но вы вычисляете txtHash = -q+0xdead. Эти два значения математически равны mod q, но отличаются от Java, взятого % q.