Z-Algorithm: How Far Does Each Position Match the Start?

The Z-algorithm answers a focused question for every position in a string:

Starting at this position, how many characters match the beginning of the whole string?

The answer is stored in a Z-array. If the input is a string $s$, then $Z[i]$ is the length of the longest substring beginning at position $i$ that is also a prefix of $s$.

For example, consider:

s = aabcaabxaaaz

At position $4$, the suffix is aabxaaaz. The complete string begins with aab, so the first three characters match. The next comparison is c versus x, which differs. Therefore, $Z[4] = 3$.

The important idea is not simply to compare characters quickly. A straightforward method could restart a comparison at every position and repeatedly inspect the same text. The Z-algorithm avoids much of that repeated work by maintaining a known matching interval, usually called a Z-box, written as $[L, R]$.

The interval identifies a region already known to match a prefix of the string. When the algorithm reaches another position inside that region, it reuses the earlier result instead of comparing all covered characters again. Any genuinely unknown part is checked directly.

The result is a single linear scan with time complexity $O(n)$ for a string of length $n$ and an auxiliary Z-array requiring $O(n)$ space.

1. What question does the Z-array answer?​

Let $s$ have length $n$, with positions numbered from $0$ through $n-1$.

By convention, $Z[0]$ is usually set to $0$. Position $0$ is the beginning of the complete string, so assigning it a separate conventional value keeps the rest of the array focused on matches that begin later.

For every position $i > 0$, define $Z[i]$ as the largest number $k$ for which the substring beginning at $i$ matches the prefix of length $k$:

In plain language, start at position $i$ and compare characters with the beginning of the string. Stop at the first mismatch or when the end of the string is reached. The number of successful comparisons is $Z[i]$.

For the example string, the indexed characters are:

index:  0 1 2 3 4 5 6 7 8 9 10 11
char:   a a b c a a b x a a  a  z

At position $1$, the suffix is abcaabxaaaz. It begins with a, which matches the first character of the complete string. The next comparison is b versus a, so the match stops after one character:

At position $4$, the suffix is aabxaaaz:

whole prefix: a a b c a a b x ...
from index 4: a a b x a a b x ...
               | | | mismatch

The first three characters match, but the fourth does not. Thus:

At position $8$, the suffix is aaaz, while the prefix is aabc:

prefix: a a b c
suffix: a a a z
        | | mismatch

Only the first two characters match, so $Z[8] = 2$. This detail matters because repeated a characters can make an informal visual inspection misleading.

2. Computing the example Z-array​

For aabcaabxaaaz, the completed array is:

Z = [0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 1, 0]

Here is every position in a compact table:

The nonzero values can be checked directly.

At position $1$, a matches and then b fails against a, giving $Z[1] = 1$.

At position $4$, aab matches and then x fails against c, giving $Z[4] = 3$.

At position $5$, only the first a matches because the next comparison is b versus a, giving $Z[5] = 1$.

At position $8$, aa matches and then a fails against b, giving $Z[8] = 2$.

At positions $9$ and $10$, the first a matches, but the following character is z or the string ends, giving $Z[9] = 1$ and $Z[10] = 1$.

A naive implementation can compute these values independently. The Z-algorithm produces the same array while avoiding unnecessary comparisons in overlapping regions.

3. The central idea: a known matching window​

The algorithm maintains two boundaries, $L$ and $R$. Together they define a window $[L, R]$ with the property:

In words, the substring from $L$ through $R$ matches the prefix of the string. This interval is the current Z-box.

The right boundary $R$ is particularly important. It marks the farthest position reached by a verified prefix match so far. If the next position $i$ lies outside the box, the algorithm has no earlier matching interval that safely covers it. It must begin comparing directly from the prefix.

If $i$ lies inside the box, however, the algorithm can align it with an earlier position in the prefix. The aligned index is:

Why? Position $L$ in the current window corresponds to position $0$ in the prefix. Moving $i-L$ positions to the right from $L$ corresponds to moving the same distance from position $0$ in the prefix.

For example, suppose the current box is $[4, 6]$. The text at positions $4$, $5$, and $6$ matches prefix positions $0$, $1$, and $2$. If the algorithm is processing position $5$, the aligned prefix position is:

The previously computed value $Z[1]$ contains information about a comparison that can be reused at the new position.

However, the algorithm must respect the right edge of the box. From position $i$, the number of characters still covered by the box is:

Therefore, the initial value inside the box is:

This value is guaranteed, not necessarily final. If it reaches the right edge, the algorithm may extend the match by comparing characters beyond $R$.

4. Why reuse inside the box is correct​

Assume the current Z-box is $[L, R]$. By definition, every character from $L$ through $R$ matches the corresponding character in the prefix from $0$ through $R-L$.

Now consider a position $i$ satisfying $L \leq i \leq R$. Position $i$ aligns with prefix position $i-L$. The portion from $i$ through $R$ is already known to agree with the corresponding prefix portion.

There are two important cases.

Case 1: the earlier match ends before the box edge​

Suppose:

The earlier match, when translated to the current position, ends strictly before $R$. The earlier comparison already found the reason the match stopped: a mismatch. Because the entire relevant region lies inside the verified box, the same mismatch is valid at the aligned position.

Therefore, the value can be copied exactly:

No new character comparison is needed for this position.

This is the cleanest example of avoided work. The algorithm does not recheck characters that have already been proved equal or the mismatch that has already been located in the aligned comparison.

Case 2: the earlier match reaches the box edge​

Suppose:

The previous result reaches or extends beyond the portion currently covered by the box. The box guarantees equality only through position $R$. Anything after $R$ has not yet been verified at the current alignment.

The algorithm therefore initializes:

Then it starts direct comparisons at the first position beyond the known region. If characters continue to match, $Z[i]$ grows and $R$ moves to the right. If the next character differs, the current value is complete.

This distinction gives the Z-algorithm its balance between reuse and verification:

• reuse the portion that is already known;
• compare only the portion beyond the known right boundary.

5. The algorithm step by step​

A standard implementation scans positions from left to right. It stores the Z-array and the current boundaries $L$ and $R$.

The high-level procedure is:

1. Initialize an array of zeros.
2. Set the initial window boundaries.
3. Process each position $i$ from $1$ through $n-1$.
4. If $i$ is inside the current box, initialize $Z[i]$ with the aligned value capped by the remaining box length.
5. Compare characters beyond the current known match while they agree.
6. If the new match extends farther right than the existing box, update $L$ and $R$.

Pseudocode makes the control flow precise:

z_algorithm(s):
    n = length(s)
    z = array of n zeros
    L = 0
    R = 0

    for i from 1 to n - 1:
        if i <= R:
            z[i] = min(R - i + 1, z[i - L])

        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] = z[i] + 1

        if i + z[i] - 1 > R:
            L = i
            R = i + z[i] - 1

    return z

The expression i + z[i] is the first position not yet included in the current match. The loop compares that position with prefix position z[i].

The pseudocode uses zero-based indexing. Some implementations use a slightly different initialization for an empty window or update the boundaries with equivalent expressions. Those variations are fine as long as the interval always represents a verified prefix match and the copied value is limited by the right edge.

6. Walking through important windows in the example​

The first long match begins at position $4$. The suffix beginning there is aabxaaaz, and the prefix is aabcaabxaaaz:

prefix: a a b c a a b x ...
suffix: a a b x a a b x ...
        | | | mismatch

The matching portion is aab, so the current box becomes:

At position $5$, the algorithm is inside the box. Its aligned prefix position is:

The earlier value is $Z[1] = 1$. The number of characters remaining inside the box is:

Therefore:

The algorithm then checks whether the match can extend beyond this guaranteed amount. The next comparison fails, so the final value remains $1$.

Positions $6$ and $7$ begin with b and x, respectively, while the prefix begins with a. They produce zero.

At position $8$, the suffix is aaaz. There is no useful earlier box covering the position, so the algorithm compares directly:

Thus, $Z[8] = 2$, and the new box becomes:

At position $9$, the position lies inside this new box. The aligned prefix index is:

The earlier value is $Z[1] = 1$, and only one character remains in the box:

Therefore:

No additional match can be established beyond the box because the suffix ends after one more character. Position $10$ produces another one-character match, and position $11$ begins with z, so its value is zero.

The important point is that the exact sequence of boxes may vary slightly with implementation conventions, but the invariant and final array remain the same.

7. Why the running time is linear​

The inner while loop appears capable of making the algorithm quadratic because it can compare several characters for multiple positions. The reason the total is still linear is that successful extensions move the right boundary $R$ to the right.

Whenever the algorithm compares beyond the current known box and the characters match, the verified region grows. The right boundary can move only from the beginning of the string to at most position $n-1$. It cannot move right more than $n$ times overall.

When a position is inside the current box, the algorithm first reuses a known value. It does not rescan the characters covered by that box. Any additional comparisons begin at or beyond the right edge, and successful comparisons advance that edge.

This is an amortized argument: individual iterations can perform several comparisons, but the total number of successful extensions across the entire scan is bounded by the length of the string.

The time complexity is therefore:

The algorithm stores one integer for each position in the Z-array, along with a constant amount of boundary state. Its auxiliary space is:

If the input string is included in the total memory accounting, the complete storage requirement remains linear in $n$.

8. Naive computation versus the Z-algorithm​

A direct method would compute each value independently:

1. Choose a position $i$.
2. Set one pointer to the beginning of the string.
3. Set another pointer to $i$.
4. Compare characters while they match.
5. Store the number of successful comparisons.

This approach is easy to understand and may be appropriate for a short input. Its weakness appears when many positions begin similarly. In a string containing a long run of repeated characters, several independent comparisons can inspect almost the same run again and again.

For example, in a string made mostly of a characters, a naive method may compare long sequences at position $1$, then repeat nearly the same work at position $2$, then again at position $3$. The comparisons overlap heavily.

The Z-algorithm records the first verified matching interval and uses its alignment to initialize later values. A later position may still need to compare beyond the current right boundary, but it does not blindly rescan the interior of the box.

The trade-off is that the Z-algorithm requires more careful implementation. The code must handle:

• whether $i$ is inside the current box;
• the aligned index $i-L$;
• the cap $R-i+1$;
• extensions beyond $R$;
• updates to both $L$ and $R$;
• end-of-string boundaries.

A naive implementation is simpler, but the Z-algorithm is preferable when linear-time behavior matters or when the string contains many overlapping prefix matches.

9. Using Z-values for pattern matching​

The Z-array can find occurrences of a pattern in a text by building a combined string:

pattern + separator + text

The separator must be a character that cannot occur in either the pattern or the text. Its purpose is to prevent a match from crossing the boundary between the two components.

Suppose the pattern is aba and the text is abacaba. A combined input could be:

aba#abacaba

The prefix of this combined string is the pattern. At each position belonging to the text, a Z-value equal to the pattern length means that the pattern begins at that text position.

If the pattern length is $m$ and the text length is $n$, the combined string has length approximately $m+n$. Computing its Z-array takes:

This provides a linear-time exact pattern-matching method. It is especially convenient when the same prefix-comparison mechanism is useful for both preprocessing and searching.

The separator is essential. Without a safe separator, a match could incorrectly continue from the end of the pattern into the beginning of the text and produce a Z-value that does not represent a genuine occurrence of the pattern.

The method can be used in editors, document tools, log inspection, and other text-processing components that need exact character-sequence matching. It does not by itself provide ranking, fuzzy matching, or relevance scoring; its job is to identify exact prefix-length matches.

10. Borders and repeated prefixes​

A border is a substring that is both a prefix and a suffix of a string, while being shorter than the entire string.

Z-values make border checks direct. For a string of length $n$, if:

then the suffix beginning at $i$ matches the prefix for its entire length. That suffix is therefore also a prefix, which means it is a border.

For example, suppose a string has length $8$ and $Z[5] = 3$. The suffix beginning at position $5$ has length:

Because the Z-value equals that entire suffix length, the suffix of length $3$ is also a prefix.

Borders help describe overlap and repetition. If a word ends with one of its own prefixes, another occurrence may begin before the first occurrence has completely ended. The Z-array exposes these relationships by recording how strongly each suffix aligns with the beginning of the string.

The Z-array is not the only tool for border problems. Prefix-function methods provide another common representation. The distinction is how the information is organized: the Z-array says how much of the prefix matches at each starting position, while a prefix function describes how much prefix structure remains relevant after each position.

11. Prefix occurrences and derived queries​

A Z-value also answers a family of shorter prefix questions. If $Z[i] \geq k$, then the substring of length $k$ beginning at $i$ equals the prefix of length $k$.

For example, if $Z[i] = 4$, then prefix lengths $1$, $2$, $3$, and $4$ all occur beginning at $i$. The value does not identify only one match; it describes every shorter prefix contained in that match.

This observation can support tasks such as:

• locating every occurrence of a fixed prefix;
• counting positions where a prefix of length $k$ appears;
• examining recurring beginnings throughout a string;
• identifying long repeated regions;
• studying periodic or self-similar text.

The Z-array itself does not automatically answer every aggregate query. If an application needs many counts or range queries, additional processing may be required after the array is computed. The advantage is that the character-comparison work has already been organized into one linear scan.

This makes the Z-array useful as an intermediate representation. A later stage can inspect its values, build counts, or select positions that satisfy a threshold without repeatedly comparing the original text with its prefix.

12. How the Z-box changes​

The interval $[L, R]$ is not fixed. It changes when a newly computed match reaches farther right than the current box.

Suppose the current box is $[4, 6]$. If a later position begins a match ending at position $10$, the new box becomes:

where $i$ is the starting position of that later match.

A shorter match does not replace the current box if it ends before $R$. It still receives a correct Z-value, but it does not provide a farther verified region for future positions.

This is why the algorithm stores two boundaries rather than only a single previous Z-value. The useful information is the alignment of a whole interval with the beginning of the string and the farthest verified endpoint.

A useful mental model is a ruler placed over the string. The box is a position where the text under the ruler agrees with the prefix. When the scan reaches a point under that ruler, it reads the already established alignment. Only the part beyond the ruler's end requires new comparisons.

The left boundary identifies the alignment. The right boundary identifies how far that alignment has been verified. Both are needed for correct reuse.

13. Common implementation mistakes​

Forgetting the boundary cap​

Inside the box, the copied value must be limited by the number of positions remaining through $R$:

Copying $Z[i-L]$ without this cap can claim equality beyond the region verified at the current alignment.

Using the wrong aligned index​

The corresponding prefix index is $i-L$. It is not $i$, $L$, or $R-i$. The subtraction follows directly from aligning position $L$ with prefix position $0$.

Updating the box too early​

The interval must describe a verified match. The algorithm should finish the available extension before assigning the new right endpoint. Setting $R$ to an unverified position can cause later copied values to be incorrect.

Mishandling an empty match​

If the first comparison fails, $Z[i]$ is zero. The implementation must still leave its boundary state consistent. Different implementations use different conventions for an empty window, but every maintained box must represent verified equality.

Off-by-one errors​

The number of positions from $i$ through $R$, inclusive, is:

The first position beyond the current match is $i+Z[i]$. These expressions are easy to confuse when translating the algorithm into code.

Assuming repeated letters guarantee a long match​

The example aabcaabxaaaz demonstrates why exact indexes matter. The suffix at position $8$ is aaaz, but the prefix begins aabc. The third characters are a and b, so the match length is $2$, not $3$.

Writing an index row above the string and placing the prefix and suffix side by side is a simple but effective debugging technique.

14. Testing a Z implementation​

A small collection of targeted tests can expose most boundary mistakes.

Empty input​

Define the expected behavior for a string of length zero. A common result is an empty Z-array.

One-character input​

There are no positions after index $0$, so the result contains only the chosen convention for the first position.

No repeated first character​

For a string such as:

bcdef

all later positions begin with a character different from b, so their Z-values should be zero.

Repeated characters​

For:

aaaaa

many positions have long prefix matches. This checks whether the right boundary is reused and extended correctly.

A mismatch after a long match​

In the supplied example, position $4$ matches aab and then fails at the next character. This checks whether the algorithm records the exact match length rather than continuing after a mismatch.

A match reaching the end​

Some suffixes can match a prefix all the way to the final character. Such tests verify that the comparison stops at the end of the string and does not read past the input.

Pattern-search tests​

When using a combined pattern-and-text string, test occurrences at the beginning, middle, and end of the text. Also test overlapping occurrences and confirm that the separator cannot appear in either component.

Randomized comparison​

For additional confidence, a simple implementation can be compared with a naive implementation on many short strings. The naive version is slower but easy to use as a reference for checking every Z-value.

15. Practical uses in text processing​

The Z-algorithm is a general prefix-matching tool. Its most direct practical use is exact text search: place a pattern at the beginning of a combined string, compute the Z-array, and identify positions whose values reach the pattern length.

This can be useful in editors, document tools, log inspection, and indexing components where exact character sequences matter. A search box may use additional logic for ranking or interactive behavior, but a Z-based exact comparison can serve as a lower-level matching operation.

The technique can also help analyze repeated prefixes in a document or string. If several positions have large Z-values, substantial regions beginning there agree with the beginning of the input. That information may be useful when examining repeated structure, overlapping text, or self-similar segments.

For text indexing, Z-values expose alignments with one particular string's prefix. They can help prepare data for later queries, but the Z-array is not a complete replacement for an index over many independent documents. An application that needs autocomplete across a large collection of words may prefer a trie or another shared-prefix structure.

The practical rule is to match the tool to the question:

If the question is “how much of the beginning matches at every position?”, the Z-array gives that answer directly.

16. Autocomplete and shared-prefix structures​

Autocomplete illustrates why it is useful to distinguish related string techniques.

Suppose an application stores many words and a user types a prefix. A trie can represent the words as paths whose shared beginnings occupy shared nodes. A query can follow the characters typed so far and then inspect the words below the corresponding node.

The Z-algorithm does not build a branching collection of words. It processes one string and compares each position with that string's beginning. It is therefore naturally suited to prefix relationships within one input or to comparing one pattern with one text after concatenation.

These approaches can appear in different layers of a text system. A trie may organize candidates for autocomplete, while a Z-based comparison can verify an exact relationship between a query and a particular candidate or text region. The right choice depends on whether the application needs a reusable collection index or a linear scan over one combined string.

The broader lesson is that “prefix matching” can mean several different things:

• matching a pattern against one text;
• measuring every suffix against one string's beginning;
• navigating many stored strings that share prefixes.

The Z-array addresses the second question directly and supports the first through concatenation.

17. Relationship to other string techniques​

String algorithms often avoid repeated work by storing a different kind of evidence.

A prefix-function approach records how much of a pattern's prefix remains relevant after each mismatch while a text is scanned. The Z-array instead records, at each position, how much of the complete string's prefix matches there. Both can support exact pattern matching, but their stored interpretations differ.

A rolling-hash method represents substrings with hash values so that range comparisons can be performed quickly after preprocessing. Its trade-off is that equal hashes do not automatically prove equal strings unless collisions are handled or the candidate is verified. The Z-algorithm uses direct character equality and gives a deterministic prefix-match array.

A trie shares prefixes among many stored strings and is often useful for autocomplete. It is a persistent branching index, whereas the Z-algorithm is a scan over one string.

A radix tree compresses chains of trie nodes into longer edge labels, reducing the number of explicit nodes while preserving shared-prefix navigation. Like a trie, it is designed for a collection of strings, not for measuring every position's agreement with one particular prefix.

The common principle is to preserve information that has already been established. The Z-algorithm expresses that principle through the interval $[L, R]$: the interval is compact evidence that a region has already been aligned with the prefix and does not need to be rediscovered character by character.

18. A reasoning checklist​

When reading or implementing the Z-algorithm, ask:

1. What exactly does $Z[i]$ mean at this index?
2. Which prefix position aligns with the current position?
3. Is the current position inside $[L, R]$?
4. If it is inside, how many characters are guaranteed by the box?
5. Could the match continue beyond $R$?
6. If the right boundary moves, are both $L$ and $R$ updated?
7. Does comparison stop at a mismatch or at the end of the string?
8. Is the first array value handled according to the chosen convention?
9. Are inclusive and exclusive endpoints being used consistently?

The central invariant is:

At every stage, $[L, R]$ is a verified interval whose contents equal the corresponding prefix interval.

Once this invariant is clear, the reuse formula is no longer a mysterious optimization. It follows from the alignment of the box with the prefix and from the fact that the right edge limits what has been verified.

19. Final takeaways​

The Z-algorithm turns a repeated prefix question into a linear scan. For each position $i$, it records the length of the match between the substring beginning at $i$ and the beginning of the complete string.

Its efficiency comes from three connected ideas:

• store the match length in $Z[i]$;
• maintain a verified matching window $[L, R]$;
• reuse an aligned earlier value and compare only beyond the known right edge.

The key initialization inside the window is:

The cap by $R-i+1$ protects correctness. Any successful extension moves $R$ to the right, and $R$ cannot move beyond the end of the string. Therefore, the total running time is:

The Z-array itself requires:

space.

For aabcaabxaaaz, careful indexing gives:

Z = [0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 1, 0]

Each value is a compact statement about how much of the string's beginning reappears at that position. The $[L, R]$ window is the algorithm's record of a prefix match that has already been checked and made available for reuse.

When implementing or applying the technique, begin with the definition, write indexes above the string, preserve the window invariant, and test repeated characters and boundary cases. The result is a small but powerful tool for exact prefix matching, pattern search, repeated-prefix analysis, and practical text-processing tasks where avoiding redundant comparisons matters.