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

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

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

Опр Полиномиальный хэш - функция , где - строка (и соответственно - -ый символ - иначе говоря просто число), и - основание и модуль хэширования.

Но в таком случае не выходит пересчитывать хэш подстроки по аналогии с суммой на подмассиве (через суммы на префиксах): - это не работает!

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

Опр Полиномиальный хэш (обратный) - функция .

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

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

Опр - т.е. хэш-функция на подстроке состоящей из первых символов ( от слова length, т.е. длина).

Свойство

Следствие Тогда заметьте что хэш функция подстроки длины начиная с символа : .

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

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

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

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

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 или кидать ошибку).

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

Полиномиальное хэширование + разбор интересных задач - см. про Теперь рассмотрим другой вариант выбора функции полиномиального хэширования.