The Z algorithm is a string-matching method that finds every occurrence of a pattern inside a larger text in time proportional to the combined length of the two strings. It works by building a simple auxiliary array, usually called the Z array, that records how much of the string starting at each position matches the string’s own beginning. That single data structure turns out to be surprisingly versatile, powering not just basic search but a range of problems in text processing, bioinformatics, and competitive programming.
What the Z Array Actually Tells You
Imagine you have a string of characters. For every position after the first, ask: how many characters starting here are identical to the characters at the very start of the string? The answer at each position is the Z value for that position. If the string is “aabxaab,” the Z value at position 4 is 3, because the substring “aab” starting there matches the first three characters of the string perfectly. At a position where the character doesn’t even match the first character, the Z value is zero.
The full set of these values, one per position, is the Z array. It is a compact description of every place the string echoes its own prefix. The reason this matters is that self-similarity within a string is exactly the information you need to search for a pattern efficiently. Once you know how to compute this array in linear time, pattern matching falls out almost for free.
Turning the Z Array into a Search Tool
The classic trick is concatenation. Suppose you want to find all places where a short pattern P appears inside a long text T. You glue them together with a special separator character that appears in neither P nor T, forming the string P$T (where $ is the separator). Then you compute the Z array for this combined string. Any position in the T portion whose Z value equals the full length of P marks an occurrence of the pattern in the text. The separator guarantees that a match can never “leak” across the boundary between pattern and text, so Z values in the T portion cleanly indicate real matches.
This is the entire algorithm for exact single-pattern search. There is no backtracking, no hash function, and no finite-state machine to build. You compute one array in one pass through the combined string, then read off the answer.
How It Stays Linear
The efficiency of the Z algorithm comes from a bookkeeping trick involving what is sometimes called the Z-box. As you move through the string computing Z values left to right, you keep track of the rightmost interval you have already matched against the prefix. If the current position falls inside that interval, you already know something about the characters here, because they matched earlier characters whose Z values you have already computed. You can reuse that earlier Z value as a starting point rather than comparing characters from scratch.
When the reused value tells you the match doesn’t extend past the right edge of the current interval, you are done with that position in constant time. When it does extend past the edge, you compare new characters one by one, but each new character comparison pushes the right edge further to the right. Since the right edge can only move forward and the string has a fixed length, the total number of fresh character comparisons across the entire algorithm is bounded by the length of the string. The result is that computing the Z array for a string of length n takes time proportional to n, regardless of the pattern or text content.
How It Compares to Other Pattern-Matching Algorithms
The Z algorithm belongs to a family of linear-time exact string matchers that also includes the Knuth-Morris-Pratt (KMP) algorithm, the Boyer-Moore algorithm, and the Rabin-Karp algorithm. All of them solve the same core problem, and their worst-case time complexities are broadly similar for single-pattern search. Comparative benchmarking across algorithms like Naive, KMP, Rabin-Karp, Finite Automata, Boyer-Moore, Aho-Corasick, and the Z algorithm has been carried out in multiple programming languages to test practical speed differences.1Academia.edu. Analysis of Pattern Searching Algorithms and Their Application
In practice, performance depends heavily on the alphabet size, the pattern length, and the language implementation. Boyer-Moore tends to be fastest on natural-language text with large alphabets because it can skip large chunks of the text by examining characters from the end of the pattern first. Rabin-Karp shines when you need to search for multiple patterns of the same length simultaneously, thanks to its hashing approach. KMP and the Z algorithm are close cousins in spirit: both preprocess the pattern to avoid redundant comparisons, and both guarantee linear worst-case time. The Z algorithm’s advantage is conceptual clarity. KMP relies on a “failure function” that describes where to resume matching after a mismatch, which many people find less intuitive than the Z array’s straightforward “how far does this prefix extend?” question.
For multi-pattern search, where you need to find many different patterns at once, the Aho-Corasick algorithm is the standard tool. The Z algorithm is designed for single-pattern scenarios, though its underlying ideas can be adapted to related problems.
Why Competitive Programmers Love It
The Z algorithm has an outsized reputation in competitive programming communities, and the reason is practical rather than theoretical. It is short to code, hard to get wrong, and easy to adapt. A clean implementation fits in roughly 15 to 20 lines in most languages. By contrast, a correct Boyer-Moore implementation is substantially longer, and even KMP’s failure function, while compact, requires careful index management that trips people up under contest time pressure.
More importantly, the Z array is a general-purpose tool that solves a wider class of problems than just “find this pattern in that text.” Contest problems frequently ask about string periodicity, tandem repeats, or the longest prefix that is also a suffix. All of these reduce naturally to Z-array queries. If you know how to compute the Z array, you can often solve a problem by reasoning about what configuration of Z values would answer the question, then scanning the array. This flexibility makes it one of the highest-value algorithms to memorize for competitions.
Detecting String Periodicity and Covers
A string is periodic if it can be built by repeating a shorter substring. The word “abcabcabc” has period 3 because the substring “abc” tiles the whole thing. The Z array reveals periods directly: if the Z value at position k equals the length of the string minus k, then the prefix of length k is a period of the string. You can scan the Z array once to find the shortest period, all periods, or determine that the string has no nontrivial period at all.
A related but subtler concept is a “cover.” A cover of a string is a substring that, when allowed to overlap with copies of itself, accounts for every character in the original string. The word “aba” covers “abababa” because overlapping copies of “aba” tile it completely. Computing all covers of a string can be done in linear time using a characterization based on the string’s internal structure.2Information Processing Letters. An optimal algorithm to compute all the covers of a string The Z array provides the self-similarity information that makes these kinds of analyses tractable.
Extending to Two-Dimensional Matching
Text search is not always one-dimensional. In image processing, bioinformatics (where protein structures fold in space), and certain database applications, you need to find a two-dimensional pattern inside a two-dimensional array. A natural approach is to reduce the 2D problem to a 1D problem that standard string-matching algorithms can handle. Research has shown that efficient string matching algorithms can be applied to array matching by first performing a linear preprocessing step on the text that encodes row-level or column-level matches, then running a conventional 1D matcher over the encoded result.3Communications of the ACM. A technique for two-dimensional pattern matching The Z algorithm is one of the linear-time matchers that slots neatly into this framework, since its preprocessing cost is already proportional to input size.
This reduction strategy is powerful because it means improvements to one-dimensional algorithms automatically cascade into better two-dimensional search. It also means that the Z algorithm’s simplicity becomes an engineering advantage in higher-dimensional settings, where implementation complexity can balloon quickly.
Pattern Matching on Compressed Text
Real-world data often arrives compressed. Genomic sequences, log files, and large document archives are routinely stored using compression schemes like run-length encoding, where consecutive repeated characters are stored as a single character plus a count. Decompressing the entire text just to search it is wasteful when the compressed version is much smaller.
Algorithms for dictionary matching directly on run-length encoded strings can achieve time proportional to the compressed size of the input rather than the original uncompressed length. Recent work has produced methods that, given a set of patterns and a run-length encoded text, report all matches in time that scales with the number of runs in the compressed data plus the number of matches found, with only logarithmic overhead.4Dagstuhl Publishing. Compressed Dictionary Matching on Run-Length Encoded Strings While these compressed-matching algorithms are more complex than a plain Z-algorithm implementation, they build on the same foundational ideas: preprocess the pattern’s internal structure, then exploit that structure to avoid redundant work during the scan.
Handling Wildcards and Approximate Matches
The standard Z algorithm performs exact matching: every character in the pattern must match the corresponding character in the text. But many real problems involve “don’t care” positions (wildcards) where any character is acceptable, or approximate matching where a small number of mismatches are tolerated.
Wildcard matching changes the computational landscape. When patterns contain wildcard symbols that can match any character, the average-case complexity depends on how many wildcards appear and how they are distributed. Theoretical work has established tight bounds on wildcard pattern matching, showing that when the fraction of wildcards is small the problem can still be solved in close to linear time on average, but as the fraction grows toward one the lower bound on work increases.5Theoretical Computer Science. On the average-case complexity of pattern matching with wildcards The Z algorithm itself does not natively handle wildcards, but its prefix-matching machinery can serve as a subroutine in algorithms that do, particularly when the wildcards are sparse and the pattern mostly consists of exact characters separated by a few flexible positions.
For approximate matching, where you allow up to k mismatches or edits, the Z array can speed up certain steps. One common approach is to use exact matching as a filter: compute exact matches of substrings of the pattern, then verify whether nearby positions have few enough differences to count as approximate matches. The Z array’s speed makes it a good engine for the filtering step, even though the overall approximate-matching algorithm requires additional logic.
Common Misconceptions
A persistent misconception is that the Z algorithm is somehow a lesser or simplified version of KMP. The two algorithms are equally powerful for exact single-pattern search and share the same linear time guarantee. They are built on different representations of the same underlying information: KMP’s failure function and the Z array are mathematically equivalent in the sense that either can be computed from the other in linear time. Choosing between them is a matter of taste and convenience, not capability.
Another misunderstanding is that linear-time string matching is only relevant for huge inputs. In practice, the constant factors in the Z algorithm are small, and its cache behavior is good because it scans the string mostly left to right. Even on moderately sized inputs, it handily outperforms naive quadratic search, and the implementation overhead compared to a brute-force double loop is trivial. The algorithm is worth using whenever you are doing any kind of string search, not just when the input is massive.
A third point of confusion arises around the separator character in the concatenation trick. Some people worry that they need to find a character that genuinely does not appear in the input, which feels fragile. In practice, you can use any character outside the input’s alphabet, or you can simply cap the Z values at the pattern length during computation, which achieves the same effect without needing a literal separator in memory. Many competitive-programming implementations use the sentinel approach because it is the easiest to reason about, but it is not the only option.
When the Z Algorithm Is Not the Right Tool
The Z algorithm is a single-pattern exact matcher. If you need to find dozens or hundreds of different patterns simultaneously, Aho-Corasick is the appropriate choice because it processes all patterns in one pass through the text. If you need to support fast repeated searches over the same text with different patterns, building a suffix array or suffix tree for the text and then querying it for each pattern will be faster overall, because the expensive preprocessing is done once and each query is fast.
For regular-expression matching, where the “pattern” involves alternation, repetition, and grouping, the Z algorithm does not apply at all. Regular expressions require finite automata or backtracking engines, which are fundamentally different tools. Similarly, for fuzzy or phonetic search (finding words that sound alike or are plausible misspellings), you need edit-distance algorithms or specialized indexes rather than exact prefix matching.
The Z algorithm also assumes you can hold the concatenated string P$T in memory. For extremely long texts where memory is constrained, streaming variants of KMP or online algorithms that process the text character by character without needing it all in memory at once can be more practical. The Z algorithm can be adapted to a streaming model, but the standard textbook version is not presented that way, and the adaptation requires care to maintain the Z-box invariant without random access to earlier parts of the text.
Implementing It Yourself
If you want to write the Z algorithm from scratch, the core loop is short. You maintain two variables, conventionally called L and R, that track the left and right boundaries of the rightmost Z-box you have seen so far. For each new position i, you check whether i falls inside the current Z-box. If it does, you look up the Z value of the corresponding position within the prefix (position i minus L) and use it as a starting estimate. If that estimate would take you past R, you extend character by character from R onward. If i falls outside the current Z-box entirely, you start fresh from position i and compare against the start of the string character by character. Every time you extend past R, you update L and R to reflect the new rightmost Z-box.
The trickiest part for newcomers is handling the case where the reused Z value exactly reaches the boundary of the current Z-box. In that case, you do not know whether the match extends further without checking, so you must fall through to the character-by-character extension. Getting this boundary condition wrong is the most common implementation bug. A good test case is a string of all identical characters, like “aaaaaaa,” where every Z value (after position 0) should equal the remaining length of the string. If your implementation gets that case right, it is probably correct.
Most standard-library string search functions in languages like Python, Java, or C++ use their own internal algorithms (often variants of Boyer-Moore or two-way search) that are heavily optimized for general use. You would not typically replace those with a hand-written Z algorithm for ordinary substring search. Where the Z algorithm earns its keep is in problems that go beyond simple search: finding all periods, computing prefix-suffix overlaps, solving contest problems that require the Z array as a building block, or teaching yourself how linear-time string algorithms work under the hood.