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":

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.

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.