Z Algorithm
z[i] is the longest prefix match starting at i. Inside the rightmost match box copy from the mirror, then extend.
String Matching: Z array over pattern + text
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].
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
String Matching covers these too, in the same run.