Хеширование строки означает преобразование её в число.
Более формально, мы выбираем детерминированную функцию, которая принимает строку и возвращает некоторое целочисленное значение, называемое её хешем. Детерминированная означает, что одна и та же строка всегда должна давать один и тот же хеш.
Один из самых распространённых способов определить хеш для строки — это:
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Здесь:
Например, если строка состоит из строчных английских букв, мы можем сопоставить:
'a' \to 1'b' \to 2'z' \to 26и выбрать или .
Для длинных строк значение хеша может стать очень большим, поэтому на практике мы вычисляем всё по модулю большого простого числа :
Разные строки иногда могут иметь один и тот же хеш. Это называется коллизией. В большинстве задач по спортивному программированию коллизии достаточно редки, поэтому мы обычно игнорируем их или дополнительно снижаем риск, используя двойное хеширование.
Эта версия вычисляет хеш напрямую слева направо:
Эта версия вычисляет тот же полиномиальный хеш в немного другой форме:
Дана строка длины и строка длины , мы хотим найти все позиции
такие, что
Наивное решение проверяет каждую позицию отдельно за время , что приводит к общей сложности .
Мы можем сделать лучше, используя хеширование строк.
Пусть:
hashT — хеш строки ;hashS_i — хеш подстроки .Тогда каждая позиция такая, что
является кандидатом на вхождение шаблона.
Мы можем вычислить hashT за .
Мы также можем вычислить хеш последней подстроки за .
Теперь сравним два соседних хеша подстрок:
Если мы умножим hashS_{i+1} на , мы сдвинем все степени на одну:
Тогда мы можем восстановить hashS_i как:
Это означает, что мы можем вычислять хеш каждой подстроки по следующей за времени.
Следовательно, все хеши подстрок можно вычислить суммарно за времени, и полное решение работает за:
const int P = 29;
const int M = 1e9 + 7;
vector<int> pw;
void init() {
pw.resize(N);
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = pw[i - 1] * 1ll * P % M;
}
}
int h(string s) {
int res = 0;
for (int i = 0; i < (int)s.size(); i++) {
int x = s[i] - 'a' + 1;
res = (1ll * x * pw[i] + res) % M;
}
return res;
}
int h(string s) {
int res = 0;
for (int i = (int)s.size() - 1; i >= 0; i--) {
int x = s[i] - 'a' + 1;
res = (1ll * res * P + x) % M;
}
return res;
}
vector<int> solve(string s, string t) {
int n = s.size();
int m = t.size();
if (m > n) {
return {};
}
int hashT = 0;
for (int i = 0; i < m; i++) {
hashT = (1ll * (t[i] - 'a' + 1) * pw[i] + hashT) % M;
}
vector<int> hashS(n - m + 1, 0);
for (int i = 0; i < m; i++) {
hashS[n - m] = (hashS[n - m] +
1ll * (s[n - m + i] - 'a' + 1) * pw[i]) % M;
}
for (int i = n - m - 1; i >= 0; i--) {
hashS[i] = (s[i] - 'a' + 1);
hashS[i] = (hashS[i] + 1ll * hashS[i + 1] * P) % M;
hashS[i] = (hashS[i] - 1ll * (s[i + m] - 'a' + 1) * pw[m]) % M;
hashS[i] = (hashS[i] + M) % M;
}
vector<int> res;
for (int i = 0; i <= n - m; i++) {
if (hashS[i] == hashT) {
res.push_back(i);
}
}
return res;
}