Z-Algorithm — Direct Match Lengths vs KMP

The Z-algorithm is competitive programming's go-to string tool. It solves the same problem as KMP in O(n+m), but the Z-array is directly interpretable — you see match lengths explicitly rather than reasoning about failure functions. Engineers who learned through competitive programming reach for Z-algorithm first because it is memorisable under interview pressure.

The Z-box insight that makes it linear is the exact same structural trick as KMP's failure function: maintain a rightmost matched boundary, initialise from the mirror position, only expand what has not yet been proven. Once you see this pattern, you recognise it in KMP, Manacher, and suffix array construction.

Z-Algorithm — Direct Match Lengths vs KMP

The Z-algorithm precomputes, for each position in a string, the length of the longest substring starting at that position which is also a prefix of the string. This array, called the Z-array, is built in O(n) time using a single linear scan with a sliding window that reuses previously computed matches. Unlike KMP which computes failure functions for pattern shifts, the Z-algorithm directly exposes the longest common prefix between any suffix and the whole string — a more general primitive.

To build the Z-array, maintain an interval [l, r] that represents the rightmost prefix match found so far. For each i > 0, if i ≤ r, you can initialize Z[i] from Z[i - l] (capped by r - i + 1), then extend it by character comparisons. This reuse is what gives O(n) total comparisons. The key property: Z[i] tells you exactly how many characters match the prefix starting at i, which makes substring search trivial by concatenating pattern + '$' + text and scanning for Z-values equal to pattern length.

Use the Z-algorithm when you need exact pattern matching in O(n + m) time with minimal overhead — it's simpler to implement correctly than KMP and doesn't require computing a failure table. It's especially useful in bioinformatics for exact substring search in long genomic sequences, and in text editors for find operations. The tradeoff: it uses O(n) extra space for the Z-array, while KMP uses O(m) for the failure function. For most real-world string matching, Z-algorithm's direct semantics make it easier to debug and extend.

How the Z-Algorithm Works — Plain English and Steps

The Z-algorithm computes a Z-array for a string S where Z[i] is the length of the longest substring starting at S[i] that is also a prefix of S. For example, in S='aabxaa', Z[4]=2 because S[4..5]='aa' matches the prefix 'aa'.

For pattern matching, concatenate pattern + '$' + text (the '$' is a separator not in either string). Compute the Z-array. Any position i in the text portion where Z[i] == len(pattern) is a match.

Algorithm to build the Z-array in O(n): 1. Z[0] is undefined (or set to n by convention). Maintain a window [l, r] — the rightmost Z-box found so far. 2. For each i from 1 to n-1: a. If i > r: compute Z[i] naively by matching S[i..] against S[0..]. Update l=i, r=i+Z[i]-1. b. Else (i is inside the current Z-box [l,r]): - Let k = i - l (position of i within the box, mirrored in prefix). - If Z[k] < r - i + 1: Z[i] = Z[k] (the match is entirely inside the box). - Else: extend naively from r+1 and update l and r.

The Z-box [l,r] allows us to reuse previous match results — this is what gives O(n) time instead of O(n^2).

Worked Example — Z-Array for 'aabcaab'

String S = 'aabcaab' (indices 0-6)

Z[0] = 7 by convention (entire string matches itself).

i=1: S[1..]='abcaab'. Match against prefix 'aabcaab'. S[1]='a'==S[0]='a', S[2]='b'==S[1]='a'? No. Z[1]=1. l=1,r=1. i=2: S[2..]='bcaab'. S[2]='b'!=S[0]='a'. Z[2]=0. i=3: S[3..]='caab'. S[3]='c'!=S[0]='a'. Z[3]=0. i=4: i>r(=1). S[4..]='aab'. S[4]='a'==S[0], S[5]='a'==S[1], S[6]='b'==S[2]? Yes! Z[4]=3. l=4,r=6. i=5: i=5 is inside [4,6]. k=5-4=1. Z[k]=Z[1]=1. Check: r-i+1=6-5+1=2. Z[1]=1 < 2. Z[5]=Z[1]=1. i=6: i=6 is inside [4,6]. k=6-4=2. Z[k]=Z[2]=0. Z[2]=0 < r-i+1=1. Z[6]=0.

Z-array: [7, 1, 0, 0, 3, 1, 0]

Pattern matching example: find 'aa' in text 'aabcaab'. Concatenated: 'aa$aabcaab' (length 10) Z-array: [10,1,0,2,1,0,0,3,1,0] Pattern length = 2. Look for Z[i] == 2 in the text portion (indices >= 3). Z[3]=2 -> match at text index 3-3=0. Z[7]=3 >= 2 -> match at text index 7-3=4. Matches at indices 0 and 4 in the original text.

Z-Algorithm Implementation

The implementation maintains the rightmost Z-box [l, r] to avoid redundant comparisons.

def build_z_array(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def z_search(text, pattern):
    if not pattern: return []
    combined = pattern + '$' + text
    z = build_z_array(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]

text    = 'aabcaab'
pattern = 'aa'
print('Z-array:', build_z_array('aabcaab'))
print('Matches at:', z_search(text, pattern))

Why the Z-Array Calculation Doesn't Need a PhD

The naive way to build a Z-array is O(n²). Compare each position against the prefix character by character. Works fine for a 50-character string. Useless for production data where strings hit millions of characters.

The Z-algorithm avoids this by exploiting previously computed matches. It maintains a window [left, right] — the rightmost substring that matches the prefix. When you're inside that window, you can copy Z-values from previous positions instead of re-comparing. This is the 'why' behind the linear runtime.

Here's the trick: if the current index i is within the window, Z[i] starts at min(Z[i - left], right - i + 1). You then extend it character by character. Only when you hit a mismatch or exceed the window do you update the window. This means each character gets compared at most twice — once when entering the window, once when exiting. That's how you get O(n+m) total.

The implementation below shows this using a window. No recursion. No magic. Just pointer arithmetic and a while loop.

// io.thecodeforge — dsa tutorial

public class WindowBasedZArray {
    public static int[] buildZArray(String input) {
        int n = input.length();
        int[] z = new int[n];
        int left = 0, right = 0;
        for (int i = 1; i < n; i++) {
            if (i <= right) {
                z[i] = Math.min(right - i + 1, z[i - left]);
            }
            while (i + z[i] < n && input.charAt(z[i]) == input.charAt(i + z[i])) {
                z[i]++;
            }
            if (i + z[i] - 1 > right) {
                left = i;
                right = i + z[i] - 1;
            }
        }
        return z;
    }

    public static void main(String[] args) {
        String text = "aabxaabxaa";
        String pattern = "aab";
        String combined = pattern + "$" + text;
        int[] z = buildZArray(combined);
        int patternLength = pattern.length();
        for (int i = 0; i < z.length; i++) {
            if (z[i] == patternLength) {
                System.out.println("Pattern found at index " + (i - patternLength - 1));
            }
        }
    }
}

Real-World Applications Where Z Algorithm Saves Your Neck

Pattern matching is the obvious use case, but Z-algorithm shines in places where naive approaches would melt your server.

Genome Sequence Matching: DNA strings are gigabytes long. Searching for a gene sequence (the pattern) across a genome (the text) with Z-algorithm gives you linear time. The separator character trick works because biological data has a limited alphabet — pick something that never appears naturally.

Spam Detection: Filters maintain blacklists of known spam phrases. Instead of scanning every email with a regex engine, concatenate the blacklist patterns with separators and run Z-algorithm once per email. I've seen this reduce scan time from seconds to milliseconds in production.

Plagiarism Checkers: Compare a student's submission against a corpus. Build a combined string with pattern == document, text == corpus. Z-algorithm finds exact substring matches in O(total characters). Much faster than edit distance for the initial filter.

Intrusion Detection Systems: Network packets get checked against known attack signatures. Z-algorithm handles large signature databases efficiently because it's single-pass and doesn't backtrack.

Where it fails: If your pattern or text changes frequently, rebuilding the Z-array costs O(n) each time. For dynamic data, consider suffix arrays or Aho-Corasick for multiple patterns.

// io.thecodeforge — dsa tutorial

public class GenomeSearch {
    public static void main(String[] args) {
        String genome = "AGCTTAGCAGAGCTTAGCAGAGCTTAGC";
        String gene = "AGC";
        String combined = gene + "$" + genome;
        int[] z = WindowBasedZArray.buildZArray(combined);
        int geneLen = gene.length();
        for (int i = 0; i < z.length; i++) {
            if (z[i] == geneLen) {
                System.out.println("Gene match at position " + (i - geneLen - 1));
            }
        }
    }
}

Complexity Analysis That Actually Matters

Everyone says O(n+m) time and O(n) space. That's table stakes. The interesting part is why those bounds hold and where they break.

Time Complexity: The while loop inside the for loop looks like O(n²) on first glance. But each character comparison increases the right window boundary. The right boundary only moves forward, never backward. So across the entire algorithm, each character gets compared at most two times. Total comparisons ≤ 2n. That's the tight bound. O(n+m) is just the sum of the lengths.

Space Complexity: You store one integer per character. If your string is 1GB, your Z-array is 4GB (assuming 32-bit ints). That's a problem on memory-constrained systems. Alternative: stream the string from disk and store only pattern-length suffixes? Not possible with standard Z. You need a segmented approach.

Best Case: Pattern matches at first character? Same O(n). No early exit. Unlike Boyer-Moore, Z doesn't skip characters. It's consistent.

Worst Case: All characters identical — "aaaaa". Z-array gets filled with decreasing values. Still O(n) because each position's while loop extends only as far as the prefix. The window optimizes heavily here.

Where it breaks: If the combined string length exceeds available memory, you can't build the Z-array. For truly massive datasets (tera-byte logs), you need external-memory algorithms or distributed pattern matching.

Bottom line: Z-algorithm is predictable and safe for memory-bound workloads. Know your input size before using it.

// io.thecodeforge — dsa tutorial

public class ComplexityWorstCase {
    public static void main(String[] args) {
        String allSame = "aaaaa";
        int[] z = WindowBasedZArray.buildZArray(allSame);
        // Z-array for "aaaaa": [0, 4, 3, 2, 1]
        for (int val : z) {
            System.out.print(val + " ");
        }
        System.out.println();
        long start = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            z = WindowBasedZArray.buildZArray(allSame + "b");
        }
        long end = System.nanoTime();
        System.out.println("Avg time: " + (end - start) / 1_000_000 + " ns");
    }
}

Why Z-Algorithm Smokes Naive Matching in Production

Naive string matching is O(n*m). You feel that pain the second your log files hit a million lines. Z-Algorithm crushes it to O(n+m) by preprocessing the pattern into a Z-array before a single comparison begins. That precomputation is the whole game — you pay the cost once, then matching is a linear scan.

The real advantage hits when you're matching against streaming data or repeated queries against the same pattern. KMP also gives O(n+m), but Z-Algorithm is simpler to implement correctly under a deadline. The Z-array gives you match lengths directly, no next-table gymnastics. Every senior dev I know reaches for Z when they need to grep a 2GB file and the boss is watching. It's not the most famous algorithm, but it's the one that gets the job done without edge-case nightmares.

Z-Algorithm also handles overlapping patterns naturally. That's a silent killer in naive approaches — your regex or brute-force blows up, and suddenly your monitoring pipeline is silently corrupting data. Z doesn't care. It just works.

// io.thecodeforge — dsa tutorial

public class ZMatchOverlap {
    public static void main(String[] args) {
        String text = "aaaaa";
        String pattern = "aa";
        String combined = pattern + "$" + text;
        int[] z = computeZ(combined);
        System.out.print("Matches at: ");
        for (int i = pattern.length() + 1; i < z.length; i++) {
            if (z[i] >= pattern.length()) {
                System.out.print((i - pattern.length() - 1) + " ");
            }
        }
        System.out.println();
    }

    static int[] computeZ(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r)
                z[i] = Math.min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
                z[i]++;
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}

Related Problems That Z-Algorithm Solves Without Breaking a Sweat

Z-Algorithm isn't just for finding a pattern in a string. It's the secret weapon for a class of problems that look unrelated until you see the trick. The most common: find the longest prefix of a string that also appears as a suffix. That's a direct Z-array lookup — check values at positions near the end. Another classic: count distinct substrings efficiently. Build the Z-array for suffixes and you can count without storing every substring.

Then there's the "find all palindromic substrings" problem. You combine Z with string reversal and comparison — the algorithm handles the heavy lifting of prefix matching. I've used this in production for DNA sequence analysis where palindrome detection was a filtering step. Every naive attempt O(n^3) died. Z gave us O(n^2) and fit in a single deployable class.

Finally, string compression using Z: find the smallest period of a string. If Z[i] * i == n for some i, you've found the repeating unit. This is the same trick that powers grep optimization and log deduplication tools.

// io.thecodeforge — dsa tutorial

public class ZPeriod {
    public static void main(String[] args) {
        String s = "abcabcabc";
        int[] z = computeZ(s);
        int period = s.length();
        for (int i = 1; i < s.length(); i++) {
            if (i + z[i] == s.length()) {
                period = i;
                break;
            }
        }
        System.out.println("Smallest period length: " + period);
    }

    static int[] computeZ(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r)
                z[i] = Math.min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
                z[i]++;
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}