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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
unsigned long long f = 31, p[100010], h[100010];

void buildHash(char s[]) {
    p[0] = 1;
    h[0] = s[0] - 'a' + 1;
    for (int i = 1; s[i]; i++) {
        p[i] = p[i - 1] * f;
        h[i] = h[i - 1] + p[i] * (s[i] - 'a' + 1);
    }
}

bool areEqual(int l1, int r1, int l2, int r2) {
    unsigned long long h1 = h[r1] - (l1 ? h[l1 - 1] : 0);
    unsigned long long h2 = h[r2] - (l2 ? h[l2 - 1] : 0);
    if (l1 < l2)
        h1 *= p[l2 - l1];
    if (l2 < l1)
        h2 *= p[l1 - l2];
    return h1 == h2;
}
struct Hasher {
    long long f = 31, mod = 1e9 + 7;
    vector<long long> p, h;

    Hasher(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] * f) % 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;
    }
};


 
struct Hasher {
    long long f = 31, fi = 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] * f) % mod;
            pi[i] = (pi[i - 1] * fi) % 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;
    }
};

Ссылки

Теория:

Код:

Задачи: