Rabin-Karp
Compare a rolling hash of each window with the pattern hash and read characters only on a hash hit.
Shift 0, window "abra" hashes to 57. Equal to the pattern hash 57, and the characters agree: a match at index 0.
What you will see
A hash value rolls as the window slides: subtract the leaving character, add the entering one; hits are verified.
Cost
| Best | O(n + m) |
|---|---|
| Average | O(n + m) |
| Worst | O(n * m) |
| Space | O(1) |
Worst case from hash collisions; expected linear.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.
Related
Taught by the same lesson
String Matching covers these too, in the same run.