Что делает Рабин-Карп?

Алгоритм Рабина-Карпа ищет строку pattern внутри строки text.

Например:

pattern = aba
text = abacaba

Ответ:

0 4

Потому что aba встречается в abacaba на позициях 0 и 4.

Главная идея

Вместо того чтобы сравнивать строки посимвольно, Рабин-Карп сравнивает их хеши.

Без хеша сравнение каждой подстроки может быть медленным. С хешем каждая проверка делается за 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 большие, это медленно.

Рабин-Карп через хеш

Пусть:

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

Тогда перебираем все подстроки text длины m:

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

И сравниваем их хеш с хешем pattern.

Какой хеш будем использовать?

Будем использовать полиномиальный hash:

hash = hash * P + value(symbol)

В этой реализации:

using ull = unsigned long long;

const ull P = 13331;

Почему P = 13331?

P — база полиномиального хеша. Обычно берут большое нечетное число.

13331 часто используют для string hash. Для обычных олимпиадных задач это нормальный и простой вариант.

Prefix hash

Чтобы быстро получать 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

Тогда hash подстроки можно получить за O(1).

Формула 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:

text[0...3) = aba → подходит
text[1...4) = bac → не подходит
text[2...5) = aca → не подходит
text[3...6) = cab → не подходит
text[4...7) = aba → подходит

Ответ:

0 4

Коллизии

Коллизия — это ситуация, когда две разные строки имеют одинаковый hash.

Для ULL hash шанс маленький, но теоретически он есть.

Безопасный вариант с проверкой строки

Можно сделать так: если 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;
}

Этот вариант полностью защищает от коллизий, но если совпадений хеша много, может стать медленнее.

Double hash

Чтобы сильно уменьшить шанс коллизии, можно использовать два 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 одинаковой длины

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 не имеет коллизий. Рабин-Карп проще расширять на сравнение подстрок и много patterns.

Когда использовать Рабин-Карп?

Асимптотика

Типичные ошибки

• Путать формат [l, r) и [l, r]
• Забыть посчитать массив pw
• Использовать int вместо unsigned long long
• Забыть, что hash может иметь collision
• Сравнивать подстроки разной длины только по hash
• В get написать pw[r] вместо pw[r - l]
• Брать символ как 0, например s[i] - 'a' для буквы a
• Не обработать случай, когда 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;
}

Главное запомнить