Z-Function vs KMP Failure Function in String Problems

Both the KMP failure function and the Z-function solve pattern matching in linear time and linear space, and neither one beats the other on complexity. Which one matches the shape of a given problem comes down to how each algorithm encodes the structure of a string. One looks backward, one looks forward, and that single difference in orientation decides which tool you should reach for.

Before going further, a note on names. In KMP, "failure function," "prefix function," and "LPS array" (longest proper prefix which is also suffix) all refer to the same object. The Z-function is sometimes labeled "extended KMP" in competitive programming circles. This piece uses failure function and Z-function throughout, and treats them as fixed terms rather than switching between synonyms.

What the KMP failure function stores and why it looks backward

For each index i, the failure function π[i] stores the length of the longest proper prefix of s[0…i] that also matches a suffix of that same substring. "Proper" matters here: the prefix can't be the whole substring itself, only something shorter that still lines up on both ends.

Take the pattern "ABABCABAB". Its failure function is [0,0,1,2,0,1,2,3,4]. At index 8, the value 4 says that the last four characters ending there ("ABAB") also appear as the first four characters of the whole pattern. Every value in this array answers the same kind of question: given everything scanned up to and including position i, what's the longest piece of the beginning that reappears at the end?

That's why the failure function looks backward. It doesn't care what comes after position i. It only encodes what has already been confirmed about the string's self-overlap up to that point. That is why KMP can use it to avoid re-scanning characters during a failed match: the algorithm already knows how much of the prefix survived.

What the Z-function stores

The Z-function inverts the direction. For each index i, z[i] gives the length of the longest substring starting at position i that matches a prefix of the whole string. Instead of asking what ends here, it asks how far a match starting here extends before it breaks.

A few canonical cases make the pattern concrete. For "aaaaa", the array of matching-prefix lengths is [0, 4, 3, 2, 1]: starting at each position, the run of matching a's shrinks by one each time you move right. For "aaabaab", it's [0, 2, 1, 0, 2, 1, 0]. For "abacaba", it's [0, 0, 1, 0, 3, 0, 1], where position 4 kicks off a three-character match ("aba") against the start of the string.

By convention, z[0] is set to zero rather than left as the trivial full-length match. That's just a bookkeeping choice and doesn't affect correctness anywhere the algorithm gets used.

The one conceptual difference that determines which algorithm fits which problem

Strip away the implementation detail and both arrays are answering variants of the same question: how much of a prefix matches around this position? KMP's π[i] asks what prefix of the whole string ends exactly at position i. The Z-function's z[i] asks what prefix of the whole string begins exactly at position i. Same underlying concept, opposite orientation.

That orientation is the whole ballgame. Problems built around what happens at the end of a growing prefix, or that need information to propagate backward through overlapping borders, fit KMP's chain naturally. Problems built around how far a match stretches forward from some starting point fit the Z-function's globally anchored values just as naturally. Once you can name which direction a problem is asking about, you've mostly already chosen your algorithm.

How both algorithms handle pattern search

For substring search, both algorithms lean on the same construction. Build a combined string s = pattern + separator + text, where the separator is some character guaranteed not to appear in either the pattern or the text.

Run the Z-function over this combined string; any position in the text portion where z[i] equals the pattern's length marks a match. The sentinel character blocks a match from spuriously spanning across the separator boundary into the pattern itself.

Run KMP's failure function over the same combined string, and any position where π[i] equals the pattern's length marks a match, for the identical reason. Both approaches process the concatenated string in linear time, and for straightforward pattern search, the two converge almost completely: this is the one setting where the choice between them is closest to arbitrary.

Problems where Z-function's forward, globally-anchored values are the natural fit

LeetCode 2223, Sum of Scores of Built Strings, defines the score of each built prefix si as the length of the longest common prefix between si and the full string sn, then asks for the sum of scores across every prefix. That definition is, word for word, the definition of the Z-function. Reaching for Z here isn't a clever trick, it's a direct translation of the problem statement into an array. KMP-based solutions exist, but they require routing around the mismatch in orientation to get there.

Finding the shortest repeating unit of a string works the same way. To find the smallest t such that s is built from repeated copies of t, compute the array of matching-prefix lengths and look for the first index i, where i divides the string length n, such that i + z[i] = n. That i is the period length. Because Z is forward-looking, this becomes a single linear scan with a clean stopping condition, no backward bookkeeping required.

More generally, any problem phrased as "starting from position i, how much of the beginning does the string repeat here?" is a Z-function problem by definition. There's no translation step needed, and no chain to walk: each z[i] is a self-contained answer you can read off directly.

Problems where the KMP failure function's backward chain is the natural fit

LeetCode 28, Find the Index of the First Occurrence in a String, is the textbook KMP use case. Build the LPS array, run the matching pass, return the index where it succeeds. This is the exact problem KMP was designed to solve, and the canonical implementation reads almost like the algorithm's original description.

LeetCode 214, Shortest Palindrome, can be solved with either algorithm, but KMP's route is unusually clean. Concatenate s, a separator, and the reverse of s, then compute the failure function over that combined string. The final value in the array encodes information about the largest palindromic prefix of s, making the answer recoverable without an additional pass.

Counting how many times each prefix of a string occurs elsewhere in it can be approached through the LPS array's chain of backward references, where each value points to a shorter, self-similar version of itself, a structure that the failure function naturally encodes.

A similar pattern appears when counting distinct substrings incrementally as characters get added one at a time. Adding a new character c contributes |s| + 1 minus the maximum prefix function value computed over the reversed extended string. Again, it's the backward-looking structure of π that makes an incremental update possible without recomputing everything from scratch.

Reading a problem and deciding which algorithm to reach for first

Start by isolating the exact question the problem is asking.

If it asks how far a match starting at position i extends against the beginning of the string, that's z[i], full stop. If it asks for the longest prefix of the pattern that also ends at position i, that's π[i], full stop. Questions about how prefixes and suffixes overlap throughout the string point to KMP, since the backward chain is built to encode exactly that kind of overlap. Questions about matching against a rule-generated or implicit text, where the text isn't fully materialized as a string, point toward KMP's automaton, since the Z-function needs an actual string to scan.

A softer heuristic: language about common prefixes, prefix scores, or "how much starts here" tends to signal Z. Language about borders, overlapping periods, or "what also ends here" tends to signal KMP. When neither signal is strong enough to decide the matter, default to whichever representation requires the least translation between what the problem states and what the algorithm outputs, since translation steps are where implementation bugs creep in.

The two arrays can be converted into each other in linear time, so a correct solution built on either one is always valid. The decision here is about which representation keeps the implementation legible and short. It's about which representation keeps the implementation legible and short.

Where string matching algorithms sit in broader string processing pipelines

Z-function and KMP's failure function are building blocks, not final destinations. Once a problem needs matching against many patterns at once, or answering arbitrary substring queries, the natural next step is a suffix array, a suffix tree, or Aho-Corasick, structures built for exactly that scale of question.

Even there, the two primitives don't disappear. The Z-function is connected to suffix array work, and the automaton logic behind KMP is the same idea that Aho-Corasick generalizes to handle many patterns simultaneously. Understanding these two arrays is the prerequisite for understanding how those structures work.

Practical stakes include that string matching underlies text search, preprocessing steps in data compression pipelines, and bioinformatics work such as computing shortest superstrings as a simplified model of DNA sequence assembly. At that scale, which primitive you pick affects how clean the implementation stays, and how easy it is to reason about correctness later.

The broader point runs past these two algorithms specifically. Equivalent computational power doesn't imply equivalent conceptual fit. KMP and Z solve the same class of problems in the same asymptotic time, yet picking the wrong one for a given problem still costs real implementation effort and real clarity. Choosing the encoding that matches a problem's actual structure, rather than one that merely produces the right output, is itself a meaningful part of solving it, and that lesson extends well past string algorithms.