Algorithms / Z Function

Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by Concatenation

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.

جو کم از کم جاننا ضروری ہے

Z-values measure prefix matches starting at each position.
`Z[0]` is usually defined by convention and not the main focus.
Pattern search can concatenate `pattern#text` and look for Z-values equal to the pattern length.
The maintained Z-box reuses earlier comparisons for linear time.
Z-function and prefix-function/KMP are related but different views of border structure.

اہم علامتیں

Z[i] length of longest prefix match starting at position i

Z-box [L, R] current interval matching the prefix

pattern#text concatenated string for search using a separator

مختصر حل شدہ مثال

For string `abacaba`, a position with `Z[i] = 3` means the next three characters match the prefix `aba`.
To search for pattern `aba` in text `cabaaba`, build `aba#cabaaba`.
Wherever the Z-value equals `3`, the pattern begins there in the text portion.
The maintained Z-box avoids restarting comparisons from scratch.

عام غلطیاں

Students sometimes think Z-values compare with the substring's own prefix instead of the whole string prefix.
A separator not appearing in the pattern/text is needed in concatenation search.
Z and prefix-function arrays encode related information but not the same entries.

اس قسم کے سوال کو کیسے پہچانیں

You need prefix-match lengths from every position.
Pattern search is phrased as matching the whole pattern against many text suffixes.
The solution mentions a Z-box or prefix matches.