rabin_karp.cpp

/**
 * Rabin-Karp substring search:
 *   H = (((s[0]*B + s[1])*B + s[2])... ) mod M  (val = c+1)
 * Roll: H' = ((H - val(out)*B^{L-1}) * B + val(in)) mod M
 */
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

static const std::uint64_t kMod = 1'000'000'007ULL;
static const std::uint64_t kBase = 131ULL;

static inline std::uint64_t val(unsigned char c) { return static_cast<std::uint64_t>(c) + 1; }

static std::uint64_t modMul(std::uint64_t a, std::uint64_t b) { return (a * b) % kMod; }

static std::uint64_t modPow(std::uint64_t a, std::uint64_t e) {
    std::uint64_t r = 1 % kMod;
    while (e) {
        if (e & 1) r = modMul(r, a);
        a = modMul(a, a);
        e >>= 1;
    }
    return r;
}

static std::uint64_t hashWindow(const std::string& s, std::size_t start, std::size_t len) {
    std::uint64_t h = 0;
    for (std::size_t i = 0; i < len; ++i) {
        h = (modMul(h, kBase) + val(static_cast<unsigned char>(s[start + i]))) % kMod;
    }
    return h;
}

static std::vector<std::size_t> rabinKarp(const std::string& text, const std::string& pat) {
    std::vector<std::size_t> hits;
    if (pat.empty() || pat.size() > text.size()) return hits;
    const std::size_t L = pat.size();
    const std::uint64_t hp = hashWindow(pat, 0, L);
    const std::uint64_t highPow = modPow(kBase, L - 1);  // B^{L-1}

    std::uint64_t ht = hashWindow(text, 0, L);
    auto check = [&](std::size_t start) {
        if (ht == hp && text.compare(start, L, pat) == 0) hits.push_back(start);
    };
    check(0);

    for (std::size_t start = 1; start + L <= text.size(); ++start) {
        unsigned char outc = static_cast<unsigned char>(text[start - 1]);
        unsigned char inc = static_cast<unsigned char>(text[start + L - 1]);
        ht = (ht + kMod - modMul(val(outc), highPow)) % kMod;
        ht = (modMul(ht, kBase) + val(inc)) % kMod;
        check(start);
    }
    return hits;
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pat = "ABABCABAB";
    auto pos = rabinKarp(text, pat);
    for (std::size_t p : pos) std::cout << "match at index " << p << "\n";
    return 0;
}