Существуют ли какие-либо рабочие реализации катящейся хэш-функции, используемой в строчном алгоритме поиска Рабина-Карпа?

Я хочу использовать функцию хеш-ролика, чтобы я мог принимать хэши n-граммов очень большой строки.

Например:

"stackoverflow", разбитый на 5 граммов, будет:

"stack", "tacko", "ackov", "ckove", "" kover "," overf "," verfl "," erflo "," rflow"

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

Я знаю, что в общем случае эта хэш-функция генерируется как:

H = c ₁ a ^{k - 1} + c ₂ a ^{k - 2} + c ₃ a ^{k - 3} +... + c _k a ⁰ где a - константа и c1,...., ck - входные символы.

Если вы следуете этой ссылке в строчном алгоритме поиска Rabin-Karp, в нем говорится, что "a" обычно является большим большим числом.

Я хочу, чтобы мои хэши были сохранены в 32-битных целых числах, поэтому насколько велика простое число "a", так что я не переполняю свое целое число?

Существует ли существующая реализация этой хэш-функции где-то, что я уже мог использовать?

Вот реализация, которую я создал:

public class hash2
{

    public int prime = 101;

    public int hash(String text)
    {
        int hash = 0;

        for(int i = 0; i < text.length(); i++)
        {
            char c = text.charAt(i);
            hash += c * (int) (Math.pow(prime, text.length() - 1 - i));
        }

        return hash;
    }

    public int rollHash(int previousHash, String previousText, String currentText)
    {

        char firstChar = previousText.charAt(0);
        char lastChar = currentText.charAt(currentText.length() - 1);

        int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1));
        int hash = (previousHash - firstCharHash) * prime + lastChar;

        return hash;
    }

    public static void main(String[] args)
    {
        hash2 hashify = new hash2();

        int firstHash = hashify.hash("mydog");
        System.out.println(firstHash);
        System.out.println(hashify.hash("ydogr"));
        System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr"));
    }

}

Я использую 101 как мое основное. Это имеет значение, если мои хеши будут переполняться? Я думаю, что это желательно, но я не уверен.

Это похоже на правильный путь?

Ответы

h = 0
for i from 1 to M:
  h = (h*d + c[i]) mod q

for i from 1 to lenght(c)-M:
  // first subtract the oldest character
  h = (h + d*q - c[i]*dM) mod q

  // then add the next character
  h = (h*d + c[i+M]) mod q

2^31 - sum (maxchar) * A^kx