Хеширование строк: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылки на задачи == * [http://acmp.ru/?main=task&id_task=259 ACMP #259 — A-функция от строчки] == Ссылки == * [http:…»)
 
Нет описания правки
 
(не показано 13 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Ссылки на задачи ==
h<sub>i</sub> = s<sub>0</sub>x<sup>n - 1</sup> + s<sub>1</sub>x<sup>n - 2</sup> + ... + s<sub>n - 2</sub>x + s<sub>n - 1</sub>.
* [http://acmp.ru/?main=task&id_task=259 ACMP #259 &mdash; A-функция от строчки]
 
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;
    }
};
 
{| width="100%"
| width=50% |
h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.
 
Для выравнивания хеши различных подстрок домножаются на x<sup>n - 1 - L</sup>.
 
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<sup>|L1 - L2|</sup>.
| width="10px" | &nbsp;
| width=50% |
h<sub>i</sub> = s<sub>0</sub> + s<sub>1</sub>x + s<sub>2</sub>x<sup>2</sup> + ... + s<sub>n - 1</sub>x<sup>n - 1</sup>.
 
Для выравнивания хеши различных подстрок домножаются на (x<sup>-1</sup>)<sup>L</sup>.
 
struct Hasher {
    long long x = 31, {{Changed|1=xi = 129032259,}} mod = 1e9 + 7;
    vector<long long> p, {{Changed|pi,}} h;
    Hasher(const string &s) {
        p.resize(s.size());
        {{Changed|pi.resize(s.size());}}
        h.resize(s.size());
        p[0] = {{Changed|1=pi[0] = }} 1;
        h[0] = s[0] - 'a' + 1;
        for (int i = 1; i < s.size(); i++) {
            p[i] = p[i - 1] * x % mod;
            {{Changed|1=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;
            {{Changed|1=res = (res * pi[l]) % mod}};
        }
        return res;
    }
};
|}


== Ссылки ==
== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/string_hashes e-maxx.ru &mdash; Алгоритмы хэширования в задачах на строки]
* [http://e-maxx.ru/algo/string_hashes e-maxx.ru &mdash; Алгоритмы хэширования в задачах на строки]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B2_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B5_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F._%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru &mdash; Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B2_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B5_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F._%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru &mdash; Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B4%D0%B2%D1%83%D1%85_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru &mdash; Поиск наибольшей общей подстроки двух строк с использованием хеширования]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8_%D0%B4%D0%B2%D1%83%D1%85_%D1%81%D1%82%D1%80%D0%BE%D0%BA_%D1%81_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%D0%BC_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F neerc.ifmo.ru &mdash; Поиск наибольшей общей подстроки двух строк с использованием хеширования]
* [http://github.com/indy256/codelibrary/blob/master/java/src/Hashing.java CodeLibrary &mdash; Hashing on strings]
* [https://ru.algorithmica.org/cs/hashing/polynomial/ ru.algorithmica.org — Полиномиальное хеширование]
* [http://habrahabr.ru/post/142589/ habrahabr.ru &mdash; Полиномиальные хеши и их применение]
* [http://codeforces.com/blog/entry/4898 codeforces.com &mdash; Anti-hash test]
* [http://codeforces.com/blog/entry/60445 codeforces.com — Полиномиальное хеширование + разбор интересных задач]
* [https://blog.algoprog.ru/hash-no-multiply/ Калинин П. — Про хеширование без домножения]
* [https://usaco.guide/gold/string-hashing?lang=cpp usaco.guide — String Hashing]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/hashing.cpp codelibrary/cpp/strings/hashing.cpp]
* [https://github.com/ADJA/algos/blob/master/Strings/Hashing.cpp algos/Strings/Hashing.cpp]
Задачи:
* [[:Категория: Задачи: Хеширование строк|Задачи: Хеширование строк]]


[[Категория:Строки]]
[[Категория:Строки]]

Текущая версия от 00:32, 5 марта 2024

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

Ссылки

Теория:

Код:

Задачи: