Хэш-функция на подстроке

Что если хочется в большом тексте быстро за \(O(1)\) находить хэш-функцию от произвольной подстроки?

Другая хэш-функция

Напоминание - ранее предлагалось использовать этот полиномиальный хэш:

Опр Полиномиальный хэш - функция \(hash(s) = (s[0] + s[1] \cdot p + s[2] * p^2 + s[3] \cdot p^3 + ... + s[n-1] \cdot p^{n-1}) \bmod m\), где \(s\) - строка (и соответственно \(s[i]\) - \(i\)-ый символ - иначе говоря просто число), \(p\) и \(m\) - основание и модуль хэширования.

Но в таком случае не выходит пересчитывать хэш подстроки по аналогии с суммой на подмассиве (через суммы на префиксах): \(hash(s[i...j])=hash(s[0...j]) - hash(s[0...(i-1)])\) - это не работает!

Давайте попробуем немного изменить полиномиальный хэш - пусть степени простого основания теперь идут в обратном порядке:

Опр Полиномиальный хэш (обратный) - функция \(hash2(s) = (s[0] \cdot p^{n-1} + s[1] \cdot p^{n-2} + s[2] \cdot p^{n-3} + ... + s[n-3] \cdot p^2 + s[n-2] \cdot p + s[n-1]) \bmod m\).

В таком случае рассмотрим вспомогательный хэш на префиксе:

\[pref(s, 0) = 0\] \[pref(s, 1) = s[0] \bmod m\] \[pref(s, 2) = (s[1] \cdot p + s[0]) \bmod m\]

Иначе говоря:

Опр \(pref(s, len) = hash2(s[0...(len-1)])\) - т.е. хэш-функция на подстроке состоящей из первых \(len\) символов (\(len\) от слова length, т.е. длина).

Свойство \(pref(s, len + 1) = (pref(s, len) \cdot p + s[len]) \bmod m\)

Следствие Тогда заметьте что хэш функция подстроки длины \(len\) начиная с символа \(i\): \(hash2(s[i...(i+len)]) = (pref(s, i+len) - pref(s, i) \cdot p^{len}) \bmod m\).

Основные ошибки и советы

1) Если у вас хоть где-то появились отрицательные числа - случилось переполнение целых чисел и все посыпется. Поэтому используйте везде long вместо int и берите по модулю после каждой операции.

2) Возводить основание в степень занимает много времени и портит асимптотику, поэтому все нужные вам \(p^{len}\) надо предподсчитать и сохранить в массив long[] pows (не забудьте хранить их в long и брать их по модулю после каждого домножения). Использовать Math.pow не получится и подавно - он считает степень не точно т.к. использует вещественные числа и не берет по модулю после каждого домножения.

3) Взятие по модулю знаком % не эквивалентно математической операции и возвращает числа в диапазоне от \(-(m-1)\) до \(m-1\) включительно. Поэтому используйте вместо него свою функцию которая будет эквивалентна математической, например:

static long mod(long x, long m) {
    x = x % m;
    if (x < 0) {
        x = x + m;
    }
    return x;
}

4) Удобно разбить программу на следующие функции:

static long[] calcPrefixes(String data, long p, long m)
static long calcHash(long[] pref, long[] pows, int from, int len, long p, long m), где pref - преподсчитанные в calcPrefixes(...) хэш-функции на префиксах, а pows - преподсчитанные степени основания (см. пункт 2).

5) Для отладки хорошая затея реализовать явную функцию static long calcExplicitHash(String data, int from, int len, long p, long m) и проверить что ее результат совпадает со всеми вызовами быстрой функцией calcHash (а в случае не совпадения писать в консоль FAIL или кидать ошибку).

Другая хэш-функция

Основные ошибки и советы

Рекомендуемые источники