the Z-algorithm

Take a string and, at every position, ask a simple question: starting here, how many characters in a row match the very beginning of the string? Write that count down at each position and you have built the Z-array. It is a compact fingerprint of all the ways a string echoes its own opening, and from it exact pattern matching falls out almost for free.

Formally, for a string S the value Z[i] is the length of the longest substring starting at position i that is also a prefix of S (by convention Z[0] is left undefined or set to the whole length). For S = "aabxaab": Z[1]=1 (the "a" at index 1 matches the prefix "a" but "ab"!="aa"), Z[2]=0, Z[3]=0, Z[4]=3 ("aab" at index 4 matches the prefix "aab"), and so on. The clever part is computing all Z values in O(n) total. The algorithm keeps a 'Z-box', the rightmost interval [l, r] it has confirmed equals a prefix. When it reaches a new position i inside that box, it already knows the box equals a prefix, so the character at i mirrors the character at i-l; it copies the known Z-value from there as a head start, only doing fresh character comparisons when it runs past r. Because every fresh comparison pushes r forward and r only increases, the total comparison work is linear.

To match a pattern P in a text T, build the Z-array of the combined string P + '#' + T, where '#' is a separator that appears in neither. Any position in the T part whose Z-value equals m (the pattern length) marks an exact occurrence — because m characters there match the prefix, which is P. This gives O(n+m) matching with a method many people find easier to derive and remember than KMP's failure function. The Z-array is also a Swiss-army tool for periods, repetitions, and as a stepping stone in suffix-structure constructions.