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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

hi = s0xn - 1 + s1xn - 2 + ... + sn - 2x + sn - 1.

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

    Hasher(const string &s, long long x = 31, long long mod = 1e9 + 7) : x(x), mod(mod) {
        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] * x % 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;
    }
};

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;
    }
};

Ссылки

Теория:

Код:

Задачи: