rabin_karp.h

#ifndef RABIN_KARP_H
#define RABIN_KARP_H
 
#ifdef __cplusplus
#include <string>
#include <vector>
#endif
 
namespace {
const int base = 26;
const int modulus = 1e9 + 7;

size_t compute_hash(const std::string& str, size_t start, size_t end) {
    size_t curr_mod = 1;
    size_t hash_value = 0;
    for (size_t i = start; i < end; i++) {
        hash_value = (hash_value + (size_t(str[end - i - 1]) * curr_mod) % modulus) % modulus;
        curr_mod = (curr_mod * base) % modulus;
    }
    return hash_value;
}

bool check_collision(const std::string& str1, size_t start1, const std::string& str2, size_t start2,
                     size_t length) {
    for (size_t i = 0; i < length; ++i) {
        if (str1[start1 + i] != str2[start2 + i]) {
            return false;
        }
    }
    return true;
}
} // namespace

std::vector<size_t> rabin_karp(const std::string& text, const std::string& pattern) {
    std::vector<size_t> result;
    size_t pattern_length = pattern.length();
    size_t text_length = text.length();
 
    if (pattern_length == 0) { // if pattern is empty, it can be found at every
                               // index including the end of the text
        for (size_t i = 0; i <= text_length; i++) {
            result.push_back(i);
        }
        return result;
    }
 
    if (text_length < pattern_length) { // if text is shorter than pattern,
                                        // pattern can not be found
        return result;
    }
 
    // calculate the hash of the pattern and the hash of the first pattern_length
    // characters of the text
    size_t pattern_hash = compute_hash(pattern, 0, pattern_length);
    size_t text_hash = compute_hash(text, 0, pattern_length);
 
    // the highest power used in the hash calculation of the pattern
    size_t power = 1;
    for (int i = 0; i < pattern_length - 1; ++i)
        power = (power * base) % modulus;
 
    for (size_t i = 0; i <= text_length - pattern_length; ++i) {
        if (pattern_hash == text_hash && check_collision(text, i, pattern, 0, pattern_length)) {
            result.push_back(i);
        }
 
        if (i < text_length - pattern_length) {
            text_hash =
                (base * (text_hash - ((size_t)text[i] * power % modulus) + modulus) % modulus +
                 (size_t)text[i + pattern_length]) %
                modulus;
        }
    }
 
    return result;
}
 
#endif