Что такое хеш строки?

Хеш строки — это число, которое получается из строки. Идея такая: вместо того чтобы каждый раз сравнивать строки посимвольно, мы сравниваем их хеши.

Например:

"abc" → какое-то число
"abd" → другое число

Зачем нужен хеш строки?

Хеширование строк используется, когда нужно быстро сравнивать подстроки.

Без хеша сравнение двух подстрок длины len занимает O(len). С хешем можно сравнивать за O(1).

Идея полиномиального хеша

Строку можно представить как число в системе счисления с основанием P.

Например:

s = "abc"

Тогда хеш можно представить так:

hash = a * P^2 + b * P^1 + c * P^0

В коде обычно считаем слева направо:

hash = hash * P + value(s[i])

Почему P = 13331?

P — это база хеша. Часто берут большое нечетное число.

const ull P = 13331;

Значение 13331 часто используют в строковых хешах. Оно достаточно большое и хорошо работает на практике.

Что такое ULL?

ULL — это сокращение для:

unsigned long long

В C++ удобно написать:

using ull = unsigned long long;

Тогда можно писать коротко:

ull x = 0;

Главная формула

Будем считать prefix hash:

h[0] = 0
h[i + 1] = h[i] * P + value(s[i])

Где:

Для символа можно брать:

(unsigned char)s[i] + 1

+1 нужен, чтобы символ не давал значение 0.

Степени P

Чтобы быстро получать хеш подстроки, заранее считаем степени P.

pw[0] = 1
pw[i + 1] = pw[i] * P

Тогда:

pw[i] = P^i

Код построения prefix hash

using ull = unsigned long long;

const ull P = 13331;

vector<ull> h;
vector<ull> pw;

void build(string s) {
    int n = s.size();

    h.assign(n + 1, 0);
    pw.assign(n + 1, 1);

    for (int i = 0; i < n; i++) {
        pw[i + 1] = pw[i] * P;
        h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
    }
}

Хеш подстроки

Пусть нужно получить хеш подстроки:

s[l...r-1]

То есть l включительно, r не включительно.

Формула:

get(l, r) = h[r] - h[l] * P^(r-l)

Через массив степеней:

ull get(int l, int r) {
    return h[r] - h[l] * pw[r - l];
}

Почему формула работает?

h[r] — это хеш первых r символов.

В нем есть:

s[0...l-1] + s[l...r-1]

Чтобы убрать левую часть s[0...l-1], нужно умножить h[l] на нужную степень P и вычесть.

Полный класс StringHash

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Как сравнить две подстроки?

Если есть строка s, можно сравнить две ее подстроки:

s[l1...r1-1]
s[l2...r2-1]

Если их длины равны и хеши равны, считаем, что подстроки равны.

bool equal_substrings(StringHash &hs, int l1, int r1, int l2, int r2) {
    if (r1 - l1 != r2 - l2) {
        return false;
    }

    return hs.get(l1, r1) == hs.get(l2, r2);
}

Пример сравнения подстрок

Строка:

abacaba

Подстроки:

s[0...3) = aba
s[4...7) = aba

Их хеши равны, значит подстроки одинаковые.

Полная программа: сравнение подстрок

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    StringHash hs(s);

    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;

    if (r1 - l1 == r2 - l2 && hs.get(l1, r1) == hs.get(l2, r2)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Input / Output

Input

abacaba
0 3 4 7

Output

YES

Потому что:

s[0...3) = aba
s[4...7) = aba

Если хочешь [l, r] включительно

Иногда удобнее использовать формат:

s[l...r]

Тогда функция будет такой:

ull get_inclusive(int l, int r) {
    return h[r + 1] - h[l] * pw[r - l + 1];
}

Поиск pattern в text через хеш

Нужно найти все позиции, где pattern встречается в text.

Идея:

Код поиска pattern

vector<int> find_occurrences(string pattern, string text) {
    int m = pattern.size();
    int n = text.size();

    StringHash hp(pattern);
    StringHash ht(text);

    ull need = hp.get(0, m);

    vector<int> ans;

    for (int i = 0; i + m <= n; i++) {
        if (ht.get(i, i + m) == need) {
            ans.push_back(i);
        }
    }

    return ans;
}

Время работы:

Полная программа поиска pattern

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

vector<int> find_occurrences(string pattern, string text) {
    int m = pattern.size();
    int n = text.size();

    StringHash hp(pattern);
    StringHash ht(text);

    ull need = hp.get(0, m);

    vector<int> ans;

    for (int i = 0; i + m <= n; i++) {
        if (ht.get(i, i + m) == need) {
            ans.push_back(i);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string pattern, text;

    cin >> pattern >> text;

    vector<int> ans = find_occurrences(pattern, text);

    for (int pos : ans) {
        cout << pos << ' ';
    }

    return 0;
}

Пример поиска pattern

Input

aba
abacaba

Output

0 4

Хеш для маленьких латинских букв

Если строка состоит только из a...z, можно брать:

s[i] - 'a' + 1

Тогда код построения будет:

h[i + 1] = h[i] * P + (s[i] - 'a' + 1);

Хеш палиндрома

Хеш можно использовать для проверки, является ли подстрока палиндромом.

Идея:

Код проверки палиндрома

bool is_palindrome(string s, int l, int r) {
    int n = s.size();

    string t = s;
    reverse(t.begin(), t.end());

    StringHash hs(s);
    StringHash ht(t);

    int rl = n - r;
    int rr = n - l;

    return hs.get(l, r) == ht.get(rl, rr);
}

Двойной хеш

Один ULL-хеш обычно работает хорошо, но теоретически коллизии возможны. Чтобы уменьшить шанс коллизии, можно использовать два разных хеша.

Например:

const ull P1 = 13331;
const ull P2 = 1000003;

Простой двойной ULL-хеш

using ull = unsigned long long;

struct DoubleHash {
    static const ull P1 = 13331;
    static const ull P2 = 1000003;

    vector<ull> h1;
    vector<ull> h2;
    vector<ull> p1;
    vector<ull> p2;

    DoubleHash(const string &s) {
        int n = s.size();

        h1.assign(n + 1, 0);
        h2.assign(n + 1, 0);
        p1.assign(n + 1, 1);
        p2.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            p1[i + 1] = p1[i] * P1;
            p2[i + 1] = p2[i] * P2;

            h1[i + 1] = h1[i] * P1 + x;
            h2[i + 1] = h2[i] * P2 + x;
        }
    }

    pair<ull, ull> get(int l, int r) {
        ull x = h1[r] - h1[l] * p1[r - l];
        ull y = h2[r] - h2[l] * p2[r - l];

        return {x, y};
    }
};

Хеш с mod или ULL?

Твой основной шаблон P = 13331 + ULL

Вот этот вариант можно просто запомнить и использовать:

using ull = unsigned long long;

struct Hash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    Hash() {}

    Hash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            h[i + 1] = h[i] * P + x;
            pw[i + 1] = pw[i] * P;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Как этим пользоваться?

string s;
cin >> s;

Hash hs(s);

ull x = hs.get(0, 3);
ull y = hs.get(4, 7);

if (x == y) {
    cout << "same";
} else {
    cout << "different";
}

Если:

s = abacaba

Тогда:

get(0, 3) = hash("aba")
get(4, 7) = hash("aba")

Асимптотика

Когда использовать string hash?

Типичные ошибки

• Путать формат [l, r) и [l, r]
• Забыть посчитать pw
• Использовать int вместо unsigned long long
• Забыть, что хеши могут иметь коллизии
• Сравнивать подстроки разной длины только по хешу
• Брать символ как 0, например s[i] - 'a', где для a будет 0
• Смешивать разные базы P для одной строки
• В get написать неправильную степень pw[r - l]

Короткий шаблон

using ull = unsigned long long;

const ull P = 13331;

struct Hash {
    vector<ull> h;
    vector<ull> pw;

    Hash(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            h[i + 1] = h[i] * P + x;
            pw[i + 1] = pw[i] * P;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Главное запомнить