Вопрос насчет хэшей

Решал эту задачу. Есть более простое решение - проверять длину наибольшего общего префикса и длину наибольшего общего суффикса. Но можно ли в строке s найти хэш в отрезке [1, i-1] и [i+1, n] для каждого 1 \le i \le n и проверить равен ли результат хэшу t?

Я понял, что в тупую нельзя по первому примеру:
abdrakadabra
abrakadabra

hashs_{1, 2} + hashs_{4, 12} = 63 + 237776653 = 237776716
hash_t = 357736128

Ну во-первых это зависит от хэша, ты можешь как хэш использовать хоть rand(), так что лучше уточнять какие хэши ты используешь.

Во-вторых если ты используешь полиноминальное хэширование h[i] = (h[i - 1] + s[i] * p^i) \%hsh то чтобы склеивать строки нельзя просто сложить их хэш. Если ты понимаешь хэши то ты должен понимать что идея в том что изначально хэш это полином \sum_{i=1}^{|s|} s[i] * x^i, где подставили x = p и взяли по модулю hsh(чтобы не было переполнения).

Ну и допустим мы хотим склеить строки a и b и мы знаем полиномы \sum_{i=1}^{|a|} a[i] * x^i и \sum_{i=1}^{|b|} b[i] * x^i, теперь мы получили строку s = a + b, у неё будет полином:

\sum_{i=1}^{|s|} s[i] * x^i = \sum_{i=1}^{|a|} a[i] * x^i + x^{|a|} * \sum_{i=1}^{|b|} b[i] * x^i,

дальше подумай как нужно складывать хэши чтобы получить корректный хэш конкатенации. Кстати а как ты брал хэш подстрок?

Окей. Если что напишу сюда еще.

int calc(int l, int r){
return (hs[r] - hs[l-1] * 1LL * p[r-l+1] % mod + mod) % mod;
}

разве не s_i * x^{i-1} или это необязательно?

Зависит от реализации, разницы нету, просто я обычно перестраховываюсь чтобы не выходить за границы.

1 симпатия

Можете посоветовать какие-то ресурсы для лучшего понимания хэшей? Я понимаю идею хэширования, читал этот пост в cp-algorithms и порешал немного задач. Но может есть еще полезные ресурсы?

Ну теперь смотри hs[i] = \sum_{l=1}^{r=i} s[i] * x^i так ведь?
Подстрока (L, R) в твоей функции возвращается как hs[R] - hs[L] * x^{R-L+1}, не кажется результат странным?

1 симпатия

вот блог есть.

2 симпатии

Я неправильно нахожу хэш на отрезке или вы ведете к ответу на вопрос “как нужно складывать хэши чтобы получить корректный хэш конкатенации”?

вот это, прочитай блог который я скинул там есть объяснение того как сравнивать подстроки и ± подробно расписано как всё выглядит.

1 симпатия

Там написано, что если есть строка длиной len, которая начинается в точке i, то хэш этой подстроки = (pref_{i+len} - pref_i * p^{len}) mod m. Что я делаю не так?

Ну выше я спросил как ты хэшируешь, как я понял ты хэшируешь как я, а тут другое хэширование

2 симпатии