Stringintermediatepattern-matchingz-arraylinear

Z-Algorithm

Build a Z-array to find all pattern occurrences in O(n+m).

How it works

The Z-algorithm constructs 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. To perform pattern search, the pattern P and text T are concatenated as "P$T" (the sentinel '$' prevents spurious Z-values spanning the boundary). Any position i in the text portion with Z[i] ≥ |P| marks a full pattern match.

Building the Z-array uses an expanding window [L, R] that tracks the rightmost Z-box seen so far, enabling O(1) reuse of previously computed values instead of re-extending from scratch. The full construction runs in O(n + m) time and O(n + m) space, making it linear end-to-end just like KMP. The Z-algorithm is conceptually simpler than KMP — it requires no separate failure-function phase — and is equally powerful, making it a popular choice in competitive programming and algorithms courses. Its applications extend beyond plain search: the Z-array of a single string directly reveals its string periods and repeating structure.

Complexity

Best case

O(n+m)

Average case

O(n+m)

Worst case

O(n+m)

Space

O(n)

Visualizer

Generating steps…

Where it's used in the real world

Bioinformatics / sequence alignment

Genomics primer and motif search

Tools like BWA and Bowtie use Z-function variants to locate short read sequences within reference genomes, exploiting the linear-time guarantee to process billions of base pairs efficiently.

Text compression (LZ77/LZ78)

Finding longest previous matches

LZ77-family compressors (used in gzip, zstd) need to find the longest prefix match at each position. Z-array precomputation accelerates the match-finding step, a key inner loop of the compression algorithm.

String periodicity analysis

Period and border detection in strings

Z[i] = |S| - i identifies a string period. Editors, diff tools, and data deduplication systems exploit this to detect run-length encoding opportunities and identify repeated structural units.

Implementation

function buildZArray(s: string): number[] {
  const n = s.length;
  const z = new Array<number>(n).fill(0);
  let L = 0, R = 0;

  for (let i = 1; i < n; i++) {
    if (i < R) z[i] = Math.min(R - i, z[i - L]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] > R) { L = i; R = i + z[i]; }
  }
  return z;
}

function zSearch(text: string, pattern: string): number[] {
  const m = pattern.length;
  const z = buildZArray(pattern + "$" + text);
  const matches: number[] = [];

  for (let i = m + 1; i < z.length; i++) {
    if (z[i] >= m) matches.push(i - m - 1);
  }
  return matches;
}

// Usage
console.log(zSearch("AABABAABAABAB", "AABAB")); // [3, 8]

Related algorithms

KMP String SearchLive

Find pattern in text in O(n+m) using a failure function.

O(n+m)

Rabin-KarpLive

Use a rolling hash to find pattern in text in expected O(n+m).

O(n+m)