Definition Given the sequence S and the index i, let i-th Z value of S be the length of the longest subsequence of S that starts at i and matches the prefix of S.
Example Here is an example for string "abababaca":
i:
0
1
2
3
4
5
6
7
8
S:
a
b
a
b
a
b
a
c
a
Z:
9
0
5
0
3
0
1
0
1
Summary The z-algorithm vocabulary implements algorithm for finding all Z values for sequence S in linear time. In contrast to naive approach which takes Θ(n^2) time.