Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by Concatenation
Open lesson
The Z-function at position
i stores the length of the longest substring starting at i that matches the whole string prefix. This lets you reason about repeated prefix structure and perform pattern search via concatenation.