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.

This documentation was generated offline from a
`load-all`

image. If you want, you can also
browse the documentation from within the UI developer tools. See
the Factor website
for more information.

Factor 0.99 x86.64 (2203, heads/master-424edf64aa, Mar 8 2023 13:48:50)