The Z-array of a string S stores, for each index i, the length of the longest substring starting at i that matches a prefix of S. Compute it once over the concatenation pattern + $ + text and every Z[k] equal to |pattern| marks a match — in linear time, with no failure function.
Think of the deepest prefix-match window we've ever seen so far. Maintain [L, R], the rightmost interval such that S[L..R] equals S[0..R−L]. For each new index i:
i > R: no help. Compare from scratch — Z[i] = how far S[i..] matches S[0..]. If Z[i] > 0, update [L, R] = [i, i + Z[i] − 1].i ≤ R: reflect i into the prefix window. Let k = i − L. Copy Z[k] if it stays inside [L, R]; otherwise clamp to R − i + 1 and extend by naive comparison past R. Update [L, R] if the match reached past R.
Amortised, the pointer R can only move forward, so the whole build costs O(|S|). Concatenate pattern + $ + text (where $ is a character neither string contains) and any position k in the concatenation with Z[k] == |pattern| means a full match — its position in the original text is k − |pattern| − 1. Z-functions also underpin the suffix-array DC3 construction, the failure function of Aho-Corasick, and several palindromic-tree tricks.