Хэш на строках

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

Пусть нам нужно найти хеш какой-то подстроки S, начиная от символа i и заканчивая j. Коефициенты при P^i, P^(i+1), ..., P^(j) и есть символы данной подстроки. Рассмотрим многочлен h(j)-h(i-1). Он имеет вид S(i)*P^i+S(i+1)P^(i+1)+...+S(j)*P^j. Теперь, разделив все на P^i получим многочлен вида S(i)+S(i+1)*P+...+S(j)*P^j, что и будем хешем такого же вида для подстроки с i-го символа по j-й. Вместо деления можно использовать умножение на P^(N-j-1), где N - длина строки S. В таком случае получим многочлен S(i)*P^(N-j-1)+S(i+1)*P^(N-j)+...+S(j)*P^(N-1). Это в какой-то мере тоже хеш подстроки, правда уже не совсем такого вида. Но если нам нужно сравнивать только подстроки, то нам не важно, какой степени этот многочлен, а следовательно, и такая хеш функция для сравнения подстрок между собой нам подходит.

Вроде так

А насчёт коллизий - вот в недавнем моём контесте на codeforces мы попытались завалить хеш int64 - вот в той задаче (а там надо было проверять подстроку на палиндромность) вообще не удалось найти ни одного контртеста против хеша! (даже хоть с одной какой-нибудь базой P). Так что int64-хеши очень сложно завалить, не говоря уж про то, что можно в крайнем случае два int64 делать по разным базам

epic fail...
Возникла проблема в реализации.. .Когда вычисляю h(i..j) это значение иногда бывает отрицательное(понятно по какой причине).Перечитывал статью,но ошибку в самом алгоритме не нашёл.Но в коде,несмотря на то, что я ничего не понимаю в с++, меня насторожила запись в коде: "{
    h(i) = (t(i) - 'a' + 1) * p_pow(i);
    if (i)  h(i) += h(i-1);
}
"
что означает if (i)?и как избежать искажений из-за вычислений по модулю?

Почему отрицательные это я знаю.Но ведь h[j]-h[i-1] может быть меньше 0.А вот h(s1)*p^I, где s1-искомая строка-всегда больше 0.