Рабин-Карп не істейді?

Рабин-Карп алгоритмі pattern строкасын text ішінде іздейді.

Мысалы:

pattern = aba
text = abacaba

Answer:

0 4

Себебі aba строкасы abacaba ішінде 0 және 4 позицияларында кездеседі.

Негізгі идея

String-терді әр символ бойынша салыстырудың орнына, Рабин-Карп олардың hash мәндерін салыстырады.

Hash жоқ болса, әр substring салыстыру баяу болуы мүмкін. Hash арқылы әр тексеру O(1).

Наивный поиск

Қарапайым әдіс: pattern-ді text-тің әр позициясына қойып, символдарды салыстыру.

for (int i = 0; i + m <= n; i++) {
    bool ok = true;

    for (int j = 0; j < m; j++) {
        if (text[i + j] != pattern[j]) {
            ok = false;
            break;
        }
    }

    if (ok) {
        cout << i << ' ';
    }
}

Уақыты:

Егер n және m үлкен болса, бұл баяу.

Рабин-Карп hash арқылы

Болсын:

m = pattern.size()
n = text.size()

text ішіндегі ұзындығы m барлық substring-ді қараймыз:

text[0...m)
text[1...m+1)
text[2...m+2)
...

Әр substring hash-ін pattern hash-імен салыстырамыз.

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

Полиномиальный hash қолданамыз:

hash = hash * P + value(symbol)

Осы реализацияда:

using ull = unsigned long long;

const ull P = 13331;

Неге P = 13331?

P — полиномиальный hash базасы. Әдетте үлкен тақ сан алынады.

13331 string hash үшін жиі қолданылады. Көп олимпиадалық есептер үшін бұл қарапайым және жақсы вариант.

Prefix hash

Кез келген substring hash-ін тез алу үшін алдын ала prefix hash санаймыз.

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

Сонымен бірге P дәрежелерін санаймыз:

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

Сонда substring hash O(1) уақытта табылады.

Substring hash формуласы

Формат:

s[l...r)

Бұл: l кіреді, r кірмейді.

Формула:

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

Код:

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

Базалық Hash класы

using ull = unsigned long long;

const ull P = 13331;

struct Hash {
    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];
    }
};

Неге value = (unsigned char)s[i] + 1?

Символды санға айналдыру керек. Универсальный вариант:

ull x = (unsigned char)s[i] + 1;

Бұл тек a...z емес, басқа символдарға да жұмыс істейді.

Рабин-Карп коды

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

    vector<int> ans;

    if (m > n) {
        return ans;
    }

    Hash hp(pattern);
    Hash ht(text);

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

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

    return ans;
}

Мұнда:

Толық программа

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

using ull = unsigned long long;

const ull P = 13331;

struct Hash {
    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];
    }
};

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

    vector<int> ans;

    if (m > n) {
        return ans;
    }

    Hash hp(pattern);
    Hash ht(text);

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

    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 = rabin_karp(pattern, text);

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

    return 0;
}

Input / Output

Input

aba
abacaba

Output

0 4

Мысалды разбор

Берілген:

pattern = aba
text = abacaba

Pattern ұзындығы:

m = 3

Text ішіндегі ұзындығы 3 substring-терді тексереміз:

text[0...3) = aba → жарайды
text[1...4) = bac → жарамайды
text[2...5) = aca → жарамайды
text[3...6) = cab → жарамайды
text[4...7) = aba → жарайды

Answer:

0 4

Collision

Collision — екі әртүрлі string-тің hash мәні бірдей болып қалуы.

ULL hash үшін шанс өте аз, бірақ теориялық түрде бар.

Қауіпсіз вариант: string-ті қосымша тексеру

Егер hash тең болса, қосымша compare арқылы нақты тексереміз.

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

    vector<int> ans;

    if (m > n) {
        return ans;
    }

    Hash hp(pattern);
    Hash ht(text);

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

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

    return ans;
}

Бұл вариант collision-нан толық қорғайды, бірақ hash совпадение көп болса, баяулау болуы мүмкін.

Double hash

Collision шансын қатты азайту үшін екі ULL hash қолдануға болады.

Double 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() {}

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

    void build(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;

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

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

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

Рабин-Карп double hash арқылы

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

    vector<int> ans;

    if (m > n) {
        return ans;
    }

    DoubleHash hp(pattern);
    DoubleHash ht(text);

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

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

    return ans;
}

Бірнеше pattern іздеу

Рабин-Карп бірнеше бірдей ұзындықтағы pattern іздеуге ыңғайлы.

Идея:

Бірдей ұзындықтағы бірнеше pattern коды

vector<int> find_many_patterns(vector<string> patterns, string text) {
    vector<int> ans;

    if (patterns.empty()) {
        return ans;
    }

    int m = patterns[0].size();
    int n = text.size();

    unordered_set<ull> st;

    for (string p : patterns) {
        if ((int)p.size() == m) {
            Hash hp(p);
            st.insert(hp.get(0, m));
        }
    }

    Hash ht(text);

    for (int i = 0; i + m <= n; i++) {
        ull cur = ht.get(i, i + m);

        if (st.count(cur)) {
            ans.push_back(i);
        }
    }

    return ans;
}

Рабин-Карп және KMP

KMP-де collision болмайды. Рабин-Карп substring салыстыруға және көп pattern іздеуге ыңғайлы.

Рабин-Карп қашан қолданылады?

Асимптотика

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

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

Қысқа Hash шаблоны

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

Қысқа Рабин-Карп шаблоны

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

    vector<int> ans;

    if (m > n) {
        return ans;
    }

    Hash hp(pattern);
    Hash ht(text);

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

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

    return ans;
}

Ең бастысы