AlgoScope

Z Algorithm

z[i] is the longest prefix match starting at i. Inside the rightmost match box copy from the mirror, then extend.

String algorithms, algorithm, intermediate
z at 1 is 1.012345678910111213szaab$aabxaabaab1

String Matching: Z array over pattern + text

Decision, step 2 of 15

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].

How string matching works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

Taught by the same lesson

String Matching covers these too, in the same run.