Z Algorithm
z[i] is the longest prefix match starting at i; inside the rightmost match box copy from the mirror, then extend.
i = 1. Outside the box, so compare from scratch. Comparing extends it by 1. z[1] = 1. That reaches further right than the box, so the box becomes [1, 1].
What you will see
The Z-box slides and stretches; values inside the box are copied, values outside are extended by comparison.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(n) |
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.
Before this
Related
Taught by the same lesson
String Matching covers these too, in the same run.