String hash деген не?

String hash — string-тен алынатын бір сан. Идея: string-терді әр символ бойынша салыстырмай, олардың hash мәндерін салыстыру.

Мысалы:

"abc" → бір сан
"abd" → басқа сан

String hash не үшін керек?

String hash көбіне substring-терді тез салыстыру үшін қолданылады.

Hash жоқ болса, ұзындығы len екі substring салыстыру O(len). Hash болса, салыстыру O(1).

Полиномиальный hash идеясы

String-ті P негізіндегі сан сияқты қарауға болады.

Мысалы:

s = "abc"

Hash былай көрінеді:

hash = a * P^2 + b * P^1 + c * P^0

Кодта көбіне солдан оңға қарай санаймыз:

hash = hash * P + value(s[i])

Неге P = 13331?

P — hash базасы. Көбіне үлкен тақ сан алады.

const ull P = 13331;

13331 string hash үшін жиі қолданылатын база. Практикада жақсы жұмыс істейді.

ULL деген не?

ULL деген:

unsigned long long

C++ ішінде қысқа жазу үшін:

using ull = unsigned long long;

Енді былай жазуға болады:

ull x = 0;

Негізгі формула

Prefix hash санаймыз:

h[0] = 0
h[i + 1] = h[i] * P + value(s[i])

Мұнда:

Символ үшін универсальный вариант:

(unsigned char)s[i] + 1

+1 керек, себебі символдың мәні 0 болып кетпегені жақсы.

P дәрежелері

Substring hash-ін тез алу үшін алдын ала P дәрежелерін санаймыз.

pw[0] = 1
pw[i + 1] = pw[i] * P

Сонда:

pw[i] = P^i

Prefix hash құру коды

using ull = unsigned long long;

const ull P = 13331;

vector<ull> h;
vector<ull> pw;

void build(string s) {
    int n = s.size();

    h.assign(n + 1, 0);
    pw.assign(n + 1, 1);

    for (int i = 0; i < n; i++) {
        pw[i + 1] = pw[i] * P;
        h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
    }
}

Substring hash

Мына substring hash-ін алғымыз келеді:

s[l...r-1]

Яғни l кіреді, r кірмейді.

Формула:

get(l, r) = h[r] - h[l] * P^(r-l)

pw массивімен:

ull get(int l, int r) {
    return h[r] - h[l] * pw[r - l];
}

Неге формула жұмыс істейді?

h[r] — алғашқы r символдың hash-і.

Оның ішінде бар:

s[0...l-1] + s[l...r-1]

Сол жақ бөлікті s[0...l-1] алып тастау үшін h[l]-ді керек P дәрежесіне көбейтіп, азайтамыз.

Толық StringHash класы

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Екі substring қалай салыстырылады?

Бір string ішінде екі substring берілсін:

s[l1...r1-1]
s[l2...r2-1]

Егер ұзындықтары тең және hash-тері тең болса, substring-терді бірдей деп санаймыз.

bool equal_substrings(StringHash &hs, int l1, int r1, int l2, int r2) {
    if (r1 - l1 != r2 - l2) {
        return false;
    }

    return hs.get(l1, r1) == hs.get(l2, r2);
}

Substring салыстыру мысалы

String:

abacaba

Substring-тер:

s[0...3) = aba
s[4...7) = aba

Олардың hash-тері тең, демек substring-тер бірдей.

Толық программа: substring салыстыру

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    StringHash hs(s);

    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;

    if (r1 - l1 == r2 - l2 && hs.get(l1, r1) == hs.get(l2, r2)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Input / Output

Input

abacaba
0 3 4 7

Output

YES

Себебі:

s[0...3) = aba
s[4...7) = aba

Егер [l, r] inclusive керек болса

Кейде мына формат ыңғайлы:

s[l...r]

Онда функция былай болады:

ull get_inclusive(int l, int r) {
    return h[r + 1] - h[l] * pw[r - l + 1];
}

Hash арқылы pattern іздеу

pattern string-і text ішінде қай позицияларда кездесетінін табу керек.

Идея:

Pattern іздеу коды

vector<int> find_occurrences(string pattern, string text) {
    int m = pattern.size();
    int n = text.size();

    StringHash hp(pattern);
    StringHash ht(text);

    ull need = hp.get(0, m);

    vector<int> ans;

    for (int i = 0; i + m <= n; i++) {
        if (ht.get(i, i + m) == need) {
            ans.push_back(i);
        }
    }

    return ans;
}

Жұмыс уақыты:

Толық программа: pattern іздеу

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct StringHash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    StringHash() {}

    StringHash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            pw[i + 1] = pw[i] * P;
            h[i + 1] = h[i] * P + (unsigned char)s[i] + 1;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

vector<int> find_occurrences(string pattern, string text) {
    int m = pattern.size();
    int n = text.size();

    StringHash hp(pattern);
    StringHash ht(text);

    ull need = hp.get(0, m);

    vector<int> ans;

    for (int i = 0; i + m <= n; i++) {
        if (ht.get(i, i + m) == need) {
            ans.push_back(i);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string pattern, text;

    cin >> pattern >> text;

    vector<int> ans = find_occurrences(pattern, text);

    for (int pos : ans) {
        cout << pos << ' ';
    }

    return 0;
}

Pattern іздеу мысалы

Input

aba
abacaba

Output

0 4

Кіші латын әріптері үшін hash

Егер string тек a...z әріптерінен тұрса, былай алуға болады:

s[i] - 'a' + 1

Сонда build ішінде:

h[i + 1] = h[i] * P + (s[i] - 'a' + 1);

Palindrome hash

Hash арқылы substring palindrome екенін тексеруге болады.

Идея:

Palindrome тексеру коды

bool is_palindrome(string s, int l, int r) {
    int n = s.size();

    string t = s;
    reverse(t.begin(), t.end());

    StringHash hs(s);
    StringHash ht(t);

    int rl = n - r;
    int rr = n - l;

    return hs.get(l, r) == ht.get(rl, rr);
}

Double hash

Бір ULL hash көбіне жақсы жұмыс істейді, бірақ теориялық collision мүмкін. Collision шансын азайту үшін екі түрлі hash қолдануға болады.

Мысалы:

const ull P1 = 13331;
const ull P2 = 1000003;

Қарапайым double ULL hash

using ull = unsigned long long;

struct DoubleHash {
    static const ull P1 = 13331;
    static const ull P2 = 1000003;

    vector<ull> h1;
    vector<ull> h2;
    vector<ull> p1;
    vector<ull> p2;

    DoubleHash(const string &s) {
        int n = s.size();

        h1.assign(n + 1, 0);
        h2.assign(n + 1, 0);
        p1.assign(n + 1, 1);
        p2.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            p1[i + 1] = p1[i] * P1;
            p2[i + 1] = p2[i] * P2;

            h1[i + 1] = h1[i] * P1 + x;
            h2[i + 1] = h2[i] * P2 + x;
        }
    }

    pair<ull, ull> get(int l, int r) {
        ull x = h1[r] - h1[l] * p1[r - l];
        ull y = h2[r] - h2[l] * p2[r - l];

        return {x, y};
    }
};

Hash mod арқылы ма, әлде ULL ма?

Негізгі шаблон: P = 13331 + ULL

Мына вариантты жаттап алып қолдануға болады:

using ull = unsigned long long;

struct Hash {
    static const ull P = 13331;

    vector<ull> h;
    vector<ull> pw;

    Hash() {}

    Hash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            h[i + 1] = h[i] * P + x;
            pw[i + 1] = pw[i] * P;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Қалай қолданамыз?

string s;
cin >> s;

Hash hs(s);

ull x = hs.get(0, 3);
ull y = hs.get(4, 7);

if (x == y) {
    cout << "same";
} else {
    cout << "different";
}

Егер:

s = abacaba

Онда:

get(0, 3) = hash("aba")
get(4, 7) = hash("aba")

Асимптотика

String hash қашан қолданылады?

Типтік қателер

• [l, r) және [l, r] форматтарын шатастыру
• pw массивін санауды ұмыту
• unsigned long long орнына int қолдану
• Hash collision болуы мүмкін екенін ұмыту
• Ұзындығы әртүрлі substring-терді тек hash бойынша салыстыру
• Символды 0 қылып алу, мысалы s[i] - 'a', мұнда a үшін 0 болады
• Бір string үшін әртүрлі P базаларын араластыру
• get ішінде pw[r - l] дәрежесін қате жазу

Қысқа шаблон

using ull = unsigned long long;

const ull P = 13331;

struct Hash {
    vector<ull> h;
    vector<ull> pw;

    Hash(const string &s) {
        int n = s.size();

        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            ull x = (unsigned char)s[i] + 1;

            h[i + 1] = h[i] * P + x;
            pw[i + 1] = pw[i] * P;
        }
    }

    ull get(int l, int r) {
        return h[r] - h[l] * pw[r - l];
    }
};

Ең бастысы