How Rabin-Karp String Matching Works

The initial hash loop computes three values in one pass. p_hash and text_hash are both built by the same Horner's method recurrence: multiply the running hash by alphabet_size and add the next character's ordinal, all modulo modulus. After the loop, both are the polynomial hash of their respective length-m strings. The third accumulator, modulus_power, tracks the value of alphabet_size raised to the power of m - 1, which is needed in the rolling-hash step to subtract the outgoing character's contribution. The continue on line 37 skips the modulus-power update on the last iteration, because the rolling hash never needs alphabet_size^m; it only needs up to alphabet_size^(m-1). This is the only loop that reads the pattern; the pattern pointer never moves after this.

The sliding-window loop is where the rolling hash pays off. Each iteration checks whether the current window's hash matches the pattern hash. If they match, an exact string comparison on line 42 confirms the hit and returns immediately, handling the case where two different strings happen to produce the same hash value modulo modulus. If the window does not match or produces a hash collision, the hash is updated by the rolling recurrence on lines 47 to 50: subtract ord(text[i]) * modulus_power (the outgoing character's contribution scaled to its position), multiply the result by alphabet_size (shift all remaining characters one position left in the polynomial), and add the new character entering the window from the right. The continue on line 44 skips the update at the last position because there is no next window to hash.

The test function wraps all assertions in a single callable so CI can verify the entire test suite through a single doctest: test_rabin_karp() prints Success. only after all asserts pass. This is a deliberate design choice, because individual assert statements do not produce doctest-compatible output. Test 1 uses the same repeated-prefix pattern as the KMP test file, which is a good stress test for rolling hashes: the pattern appears in text1 but not in text2, and a naive implementation might report a false match if the rolling hash coincidentally collides at the position where the partial prefix appears in text2. Test 5 uses a two-byte UTF-8 character "Lü" to verify that the 256-base hash correctly handles multi-byte code points by treating each byte as a separate element.

The correctness guarantee rests on line 42. A hash match is a necessary but not sufficient condition for a true match: two different strings of the same length can produce the same value modulo modulus, which would give a false positive if the function returned on hash equality alone. The and text[i : i + p_len] == pattern clause on the same line performs a full character-by-character comparison only when the hashes agree, so false positives are caught before the function returns True. The expected cost of this confirmation step is O(m) per hash collision, but with a prime modulus of around one million the expected number of collisions over a length-n text is approximately n divided by one million, making the total cost of all confirmations negligible in practice. The two-level filter design is the canonical Rabin-Karp pattern.