Rabin-Karp hashes the pattern and each text window of equal length. Matching hashes trigger direct comparison to handle collisions. Rolling hash updates each window in O(1), giving near-linear performance in practice.
vector<int> rabinKarp(string text, string pat) {
const long long B = 256, MOD = 1000000007;
int n = text.size(), m = pat.size();
if (m > n) return {};
long long hp = 0, ht = 0, h = 1;
for (int i = 0; i < m - 1; i++) h = (h * B) % MOD;
for (int i = 0; i < m; i++) {
hp = (hp * B + pat[i]) % MOD;
ht = (ht * B + text[i]) % MOD;
}
vector<int> res;
for (int i = 0; i <= n - m; i++) {
if (hp == ht && text.substr(i, m) == pat) res.push_back(i);
if (i < n - m) {
ht = (B * (ht - text[i] * h % MOD + MOD) + text[i + m]) % MOD;
}
}
return res;
}Avoids recomputing each window hash from scratch by updating in O(1).
Equal hashes are verified by direct substring comparison.
Good for multiple-pattern checks and plagiarism-like scanning workflows.
Quiz coming soon for this algorithm.