Prefix Function
For each prefix, the length of its longest proper prefix that is also a suffix, built by falling back through shorter borders.
Decision · step 2 of 7String Matching: Prefix function of a pattern
i = 1, prefix "ab". Start from pi[0] = 0. No border can be extended, so pi[1] = 0.
What you will see
A second row fills under the pattern; on mismatch the length falls back to the previous value.
Cost
| Best | O(m) |
|---|---|
| Average | O(m) |
| Worst | O(m) |
| Space | O(m) |
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
Taught by the same lesson
String Matching covers these too, in the same run.