When a fixed-size window slides across a string, recomputing its hash from every character repeats work. A rolling hash reuses the previous window’s hash: remove the outgoing character’s contribution and add the incoming character’s contribution. This updates the hash in constant time per shift. section 4.0 section 4.4
Slide from ALI to LIC
Map letters to numbers: A=1, L=12, I=9, C=3. With a simple sum hash, ALI hashes to 22. When the window shifts, subtract A’s value and add C’s: 22 − 1 + 3 = 24, the hash for LIC. A positional hash can distinguish more strings: for example, using powers of 10 gives characters different place values. Its rolling update removes the outgoing character’s weighted contribution before adding the new character. section 4.1
A hash match is only a candidate match: different substrings can collide and produce the same value. Rabin–Karp therefore checks the actual characters whenever hashes match. A weak hash can cause frequent collisions and repeated checks, making performance degrade to O(n × m); the average and best cases are O(n + m). section 4.1 section 4.0
