Rabin-Karp Algorithm
Key Insight
Compare hash values instead of strings. If hash(window) != hash(pattern), definitely no match. Only verify character-by-character when hashes match (may be a collision).
Rolling Hash Formula
Treat string as a number in base d (typically 256 for ASCII), mod a prime q:
h(s[i..i+m-1]) = s[i]*d^(m-1) + s[i+1]*d^(m-2) + ... + s[i+m-1]To slide window from position i to i+1 in O(1):
new_hash = (d * (old_hash - s[i] * d^(m-1)) + s[i+m]) mod q
[Description truncada. Veja o README completo no GitHub.]