DefinitionGiven 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.
ExampleHere 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 |
SummaryThe
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.