Skip to main content
Pattern Matching

Z Algorithm

Build a Z-array where Z[i] = length of the longest substring starting at i that matches a prefix of the string. To find pattern in text, concatenate pattern + '$' + text and compute Z-array. Any Z[i] = len(pattern) is a match.

O(n + m)
·
O(n + m)
say this out loud

The Z array records the longest prefix match at every position, which answers both matching and periodicity in a single linear pass.

How It Works

The Z-array of a string stores, at each position i, the length of the longest substring starting at i that matches a prefix of the whole string. It is computed in O(n) by maintaining the rightmost 'Z-box' (an interval known to match the prefix) and initializing each new Z value from the corresponding position inside that box before extending by direct comparison.

For pattern matching, build the string pattern + '$' + text with a separator that appears in neither part. Any position in the text section whose Z value equals the pattern length marks a full match. Total time is O(n + m), matching KMP but with an arguably more intuitive array to reason about, and the Z-array itself powers problems about borders and periodicity.

Step-by-Step Visualization

Search for "ab" in "abab" by concatenating them with a separator: "ab$abab"
a
0
b
1
$
2
a
3
b
4
a
5
b
6
separator$
1/10

Code

Java
static List<Integer> zSearch(String text, String pattern) {
  String s = pattern + "$" + text;
  int[] z = new int[s.length()];
  int l = 0, r = 0;

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

  List<Integer> results = new ArrayList<>();
  for (int i = pattern.length() + 1; i < z.length; i++)
    if (z[i] == pattern.length()) results.add(i - pattern.length() - 1);
  return results;
}

Tips & Gotchas

1Z[i] = length of longest substring starting at i that matches a prefix
2Concatenate pattern + '$' + text, then build Z-array
3Where Z[i] = pattern length, you found a match

Practice Problems

  • 1Find the Index of the First Occurrence in a String
  • 2Shortest Palindrome
  • 3Sum of Scores of Built Strings
  • 4Repeated Substring Pattern

About the Pattern Matching Pattern

Find where a pattern string appears inside a text string. Naive approach is O(n·m). KMP and Z-Algorithm achieve O(n+m) by preprocessing the pattern to avoid re-scanning characters after a mismatch.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

  • Longest Substring Without Repeating Characters
  • Valid Anagram
  • Longest Palindromic Substring
  • Minimum Window Substring
  • Group Anagrams

Frequently Asked Questions

How do the Z-array and KMP's failure function relate?

They encode equivalent prefix-matching information from opposite directions, and each can be derived from the other in linear time. Z values describe matches starting at each position, while the LPS array describes the longest prefix-suffix ending at each position; use whichever maps more directly onto your problem.

Why concatenate with a separator character like '$'?

The separator must not occur in the pattern or text so no match can spill across the boundary, which would inflate Z values past the pattern length. With it in place, checking Z[i] == pattern length is a complete and exact match test.