A matching fingerprint is a candidate
Rabin–Karp compares a pattern’s hash with the hash of each text window of the same length m. Different hashes rule out equality, but equal hashes do not prove it. A verified version compares actual characters for candidate windows. A probabilistic version can accept fingerprint equality directly, with an explicitly stated possibility of false positives. The hash here is a filtering device, not necessarily a cryptographic security primitive. As with hash-based data structures, collision behavior and assumptions about how inputs are chosen matter to both performance and the strength of the result.
Roll one window into the next
Using decimal digits for illustration, moving from window 123 to 234 subtracts the leading contribution 100, multiplies the remaining 23 by ten, and adds four. A rolling implementation performs the analogous arithmetic modulo q and precomputes r^(m−1) mod q for removing the outgoing symbol. With modulus 17, distinct windows 123 and 140 both have remainder four. Treating that equality as a verified string match is incorrect. Language-specific handling of negative remainders also matters after subtraction; normalize the result consistently instead of assuming mathematical modular arithmetic is implemented automatically.
Separate expected and worst-case work
With constant-time rolling updates and few candidates, preprocessing and scanning can take expected O(n+m)-style work under suitable hashing and input assumptions. In the verified version, however, many colliding windows can each require up to m character comparisons, giving O(nm) worst-case time. Naming a modulus without stating randomness or input assumptions is not a proof of unconditional linear behavior. Omitting verification avoids those comparisons but changes correctness guarantees. The API must make clear whether exact matches are required or whether a quantified probability of false positives is acceptable for the application.
Consider several equal-length patterns
Hashes of several patterns of one fixed length can be stored together, allowing one text window to identify candidate patterns. A matching fingerprint can still correspond to several distinct patterns, so their verification costs must be counted. Supporting arbitrarily many different pattern lengths introduces additional windows or data structures and is not automatically one constant-cost scan. Test an empty pattern, a pattern longer than the text, repetitive strings and a deliberately small modulus that produces collisions. Such tests distinguish a correct candidate filter from an implementation that silently assumes collisions never happen.