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

Настоящая польза от полиномиального хеширования начинается здесь: имея одну строку, научиться сравнивать её подстроки за константу.

Вывод формулы

Пусть $H_k$ — хеш префикса длины $k$. Тогда

$$H_k = s_0 p^{k-1} + s_1 p^{k-2} + \dots + s_{k-1}$$

А хеш подстроки $s[l..r)$ — это

$$h(l, r) = s_l p^{r-l-1} + s_{l+1} p^{r-l-2} + \dots + s_{r-1}$$

Сравним с $H_r$: там те же слагаемые, но каждое домножено ещё на что-то, плюс присутствуют лишние члены от префикса до $l$.

Заметим, что лишняя часть — это в точности $H_l$, домноженный на $p^{r-l}$. Отсюда

$$h(l, r) = H_r - H_l \cdot p^{\,r-l}$$

Ровно как вычитание префиксных сумм, только с поправочным множителем: префикс нужно «сдвинуть» на нужное число разрядов, прежде чем вычитать.

Код

struct Hasher {
    vector<long long> h, pw;

    Hasher(const string& s) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = add(mult(h[i], P), s[i] - 'a' + 1);
            pw[i + 1] = mult(pw[i], P);
        }
    }

    long long get(int l, int r) const {        // подстрока [l, r)
        return sub(h[r], mult(h[l], pw[r - l]));
    }
};

Предподсчёт — $O(n)$, каждый запрос — $O(1)$.

Проверено: на двухстах тысячах случайных строк хеш каждой подстроки, полученный этой формулой, совпал с хешем той же подстроки, посчитанным напрямую, — для всех пар границ.

Границы

В коде выше подстрока задаётся полуинтервалом $[l, r)$, а массив хешей имеет размер $n+1$ со сдвигом на единицу: h[k] — хеш префикса длины $k$.

Это то же соглашение, что у префиксных сумм, и по той же причине: не нужно писать особый случай для $l = 0$.

Если условие даёт границы включительно и с единицы, приведите их один раз при чтении, а не размазывайте -1 по всему решению. Смешение соглашений — источник ошибок, которые проявляются только на границах.

Массив степеней обязателен. Считать $p^{r-l}$ быстрым возведением в каждом запросе — лишний логарифм на пустом месте.

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

Теперь основной запрос — одна строка:

bool equalSubstrings(int l1, int r1, int l2, int r2) {
    if (r1 - l1 != r2 - l2) return false;   // разная длина
    return h.get(l1, r1) == h.get(l2, r2);
}

Проверка длин обязательна: хеши подстрок разной длины сравнивать бессмысленно, они живут в разных «системах счисления» по числу разрядов.

Две строки сразу

Если нужно сравнивать подстроки разных строк, есть два пути.

Первый: завести по объекту Hasher на каждую строку. Параметры $p$ и $m$ обязаны совпадать, иначе хеши несравнимы.

Второй, часто удобнее: склеить строки через разделитель, которого нет в алфавите, и работать с одной строкой.

string combined = a + '#' + b;

Разделитель нужен, чтобы подстроки не «перетекали» через границу. Приём стандартный и полезен далеко за пределами хешей.

Что это даёт

Практически весь дальнейший раздел:

• сравнение подстрок и наибольший общий префикс;
• период строки;
• поиск подстроки в строке — сравнить хеш образца с хешом каждого окна той же длины, $O(n)$;
• количество различных подстрок — сложить хеши всех подстрок в множество (осторожно с коллизиями: сравнений тут квадратично много);
• проверка на палиндром — сравнить хеш подстроки с хешом того же куска в развёрнутой строке.

Последний приём требует второго объекта Hasher для перевёрнутой строки и аккуратного пересчёта границ. Ошибиться в этом пересчёте легко, поэтому стоит проверить на строке из двух символов.