A rolling hash filters candidates, not proves equality
Rabin-Karp hashes the pattern and each same-length window. A polynomial hash supports removing the outgoing character and adding the incoming one without recomputing the entire window.
With base b, modulus q, and window length m, maintain h = Σ code(s[i]) × b^(m-1-i) mod q. Remove code(outgoing) × b^(m-1), normalize the remainder, multiply by b, and add the incoming code. Kotlin's remainder can be negative, so normalize subtraction deliberately.
Hash matches -> compare actual pattern and window
Hash differs -> window cannot match under the same hash function
Collisions are possible. Verifying matching hashes preserves correctness but can degrade worst-case time to O(nm) with many collisions. Randomized parameters or multiple hashes reduce collision probability but do not turn an unverified hash into a mathematical equality proof.
Exercise
Implement a small-modulus version specifically to force collisions, and verify that actual character comparison prevents false matches. Compare outputs with a naive matcher.
Check: use arithmetic whose intermediate products fit your numeric type, and include empty patterns, repeated text, and windows at the final valid start position.