Хеширование строк

h_i = s₀x^{n - 1} + s₁x^{n - 2} + ... + s_{n - 2}x + s_{n - 1}.

struct Hasher {
    long long mod;
    vector<long long> p, h;

    Hasher(const string &s, long long factor = 31, long long mod = 1e9 + 7) : mod(mod) {
        p.push_back(1);
        for (int i = 1; i < s.size(); i++)
            p.push_back(p[i - 1] * factor % mod);

        h.push_back(s[0] - 'a' + 1);
        for (int i = 1; i < s.size(); i++)
            h.push_back((h[i - 1] * factor % mod + s[i] - 'a' + 1) % mod);
    }

    long long getHash(int l, int r) {
        long long res = h[r];
        if (l)
            res = (res - p[r - l + 1] * h[l - 1] % mod + mod) % mod;
        return res;
    }
};

struct DoubleHasher { 
    Hasher h1, h2;

    DoubleHasher(const string &s) : h1(s), h2(s, 29, 1e9 + 9) {}

    pair<long long, long long> getHash(int l, int r) {
        return { h1.getHash(l, r), h2.getHash(l, r) };
    }
};

struct Hasher2D {
    long long mod;
    vector<long long> py, px;
    vector<vector<long long>> h;

    Hasher2D(const vector<string> &a, long long factorY = 29, long long factorX = 31, long long mod = 1e9 + 7) : mod(mod) {
        py.push_back(1);
        for (int y = 1; y < a.size(); y++)
            py.push_back(py[y - 1] * factorY % mod);

        px.push_back(1);
        for (int x = 1; x < a[0].size(); x++)
            px.push_back(px[x - 1] * factorX % mod);

        h.assign(a.size(), vector<long long>(a[0].size()));
        for (int y = 0; y < a.size(); y++) {
            for (int x = 0; x < a[0].size(); x++) {
                h[y][x] = (a[y][x] - 'a' + 1) % mod;
                if (y)
                    h[y][x] = (h[y][x] + h[y - 1][x] * factorY) % mod;
                if (x)
                    h[y][x] = (h[y][x] + h[y][x - 1] * factorX) % mod;
                if (y && x)
                    h[y][x] = ((h[y][x] - h[y - 1][x - 1] * factorY * factorX) % mod + mod) % mod;
            }
        }
    }

    long long getHash(int yl, int xl, int yr, int xr) {
        long long res = h[yr][xr];
        if (yl)
            res = (res - py[yr - yl + 1] * h[yl - 1][xr] % mod + mod) % mod;
        if (xl)
            res = (res - px[xr - xl + 1] * h[yr][xl - 1] % mod + mod) % mod;
        if (yl && xl)
            res = (res + py[yr - yl + 1] * px[xr - xl + 1] % mod * h[yl - 1][xl - 1]) % mod;
        return res;
    }
};

hi = s0 + s1x + s2x2 + ... + sn - 1xn - 1. Для выравнивания хеши различных подстрок домножаются на xn - 1 - L. struct Hasher { long long x = 31, mod = 1e9 + 7; vector<long long> p, h; Hasher(const string &s) { p.resize(s.size()); h.resize(s.size()); p[0] = 1; h[0] = s[0] - 'a' + 1; for (int i = 1; i < s.size(); i++) { p[i] = p[i - 1] * x % mod; h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod; } } long long getHash(int l, int r) { long long res = h[r]; if (l) res = (res - h[l - 1] + mod) % mod; res = res * p[p.size() - 1 - l] % mod; return res; } }; Этот способ непригоден для сравнения участков двух строк разной длины. В данном случае хеш более левого участка следует домножать на x|L1 - L2|.

hi = s0 + s1x + s2x2 + ... + sn - 1xn - 1. Для выравнивания хеши различных подстрок домножаются на (x-1)L. struct Hasher { long long x = 31, xi = 129032259, mod = 1e9 + 7; vector<long long> p, pi, h; Hasher(const string &s) { p.resize(s.size()); pi.resize(s.size()); h.resize(s.size()); p[0] = pi[0] = 1; h[0] = s[0] - 'a' + 1; for (int i = 1; i < s.size(); i++) { p[i] = p[i - 1] * x % mod; pi[i] = pi[i - 1] * xi % mod; h[i] = (h[i - 1] + p[i] * (s[i] - 'a' + 1) % mod) % mod; } } long long getHash(int l, int r) { long long res = h[r]; if (l) { res = (res - h[l - 1] + mod) % mod; res = (res * pi[l]) % mod; } return res; } };

Ссылки

Теория:

• e-maxx.ru — Алгоритмы хэширования в задачах на строки
• neerc.ifmo.ru — Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
• neerc.ifmo.ru — Поиск наибольшей общей подстроки двух строк с использованием хеширования
• ru.algorithmica.org — Полиномиальное хеширование
• habrahabr.ru — Полиномиальные хеши и их применение
• codeforces.com — Anti-hash test
• codeforces.com — Полиномиальное хеширование + разбор интересных задач
• Калинин П. — Про хеширование без домножения
• usaco.guide — String Hashing

Код:

• codelibrary/cpp/strings/hashing.cpp
• algos/Strings/Hashing.cpp

Задачи:

• Задачи: Хеширование строк