Zfunction
The Z-function of a string S of length n assigns to each position i the length of the longest substring starting at i that is also a prefix of S. In many algorithmic references, Z[0] is defined as 0, though some definitions take Z[0] = n. The value Z[i] thus measures how far the prefix of S matches the substring beginning at i.
Efficient computation: The Z-algorithm computes the entire Z-array in O(n) time. It maintains a window [l, r]
Applications: The Z-function is commonly used for pattern matching by forming the string P + a separator
Example: For S = "aaaaa" (with Z[0] defined as 0), the Z-array is [0, 4, 3, 2, 1].