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

unsigned long long X = 31, p[100010], h[100010];

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

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

Ссылки

Теория:

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

Код:

• CodeLibrary — Hashing on strings
• Algos — Hashing in strings based problems

Задачи:

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