Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Z Algorithm
DSA

Z Algorithm

Z Algorithm — Z-array construction, linear pattern search and longest prefix-suffix, in C++, Python, Java and JavaScript.

The Z-array answers, for every index i: how many characters starting at i match the prefix of the string?

Z[i] = length of the longest common prefix of s and s[i:].

Focus on recognizing:

“Prefix match at every position” / “linear pattern search” → Z-array

Pattern 1: Build the Z-Array

Watch the Z-array fill for "aabaab" — Z[3]=3 exposes the repeated "aab". Press ▶ to animate.

Z-Algorithm

Z-array: length of the longest prefix of s starting at each index.

Z[i] = longest substring starting at i that matches a prefix of s. Maintain a z-box [l, r]; if i is inside, Z[i] ≥ min(r-i+1, Z[i-l]), then extend. Enables O(n) substring search and underpins many string tricks.

GRID VISUALIZER
Steps –
a
a
b
a
a
b
0
1
0
3
1
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        z[0] = n (by convention)
                      
                        2
                        for i in 1..n-1:
                      
                        3
                          if inside z-box: z[i] = min(r - i + 1, z[i - l])
                      
                        4
                          extend match from i while s[z[i]] == s[i + z[i]]
                      
                        5
                          if i + z[i] - 1 > r: update box [l, r]

The trick is reusing a Z-box [l, r] — the rightmost prefix-match seen so far:

public int[] zArray(String s) {
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;              // current z-box

    for (int i = 1; i < n; i++) {
        if (i < r) {               // inside box: reuse
            z[i] = Math.min(r - i, z[i - l]);
        }

        while (i + z[i] < n
                && s.charAt(z[i]) == s.charAt(i + z[i]))
            z[i]++;                // extend match

        if (i + z[i] > r) {        // new rightmost box
            l = i;
            r = i + z[i];
        }
    }

    return z;
}
def z_array(s):
    n = len(s)
    z = [0] * n
    l = r = 0                  # current z-box

    for i in range(1, n):
        if i < r:              # inside box: reuse
            z[i] = min(r - i, z[i - l])

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

        if i + z[i] > r:       # new rightmost box
            l, r = i, i + z[i]

    return z
vector<int> zArray(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;              // current z-box

    for (int i = 1; i < n; i++) {
        if (i < r) {               // inside box: reuse
            z[i] = min(r - i, z[i - l]);
        }

        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;                // extend match

        if (i + z[i] > r) {        // new rightmost box
            l = i;
            r = i + z[i];
        }
    }

    return z;
}
function zArray(s) {
  const n = s.length;
  const z = new Array(n).fill(0);
  let l = 0,
    r = 0; // current z-box

  for (let i = 1; i < n; i++) {
    if (i < r) z[i] = Math.min(r - i, z[i - l]); // reuse

    while (i + z[i] < n && s[z[i]] === s[i + z[i]])
      z[i]++; // extend

    if (i + z[i] > r) {
      // new rightmost box
      l = i;
      r = i + z[i];
    }
  }

  return z;
}

Inside a known match? Copy z[i-l]. Then extend. Then claim the box if you reached further.

Pattern 2: Pattern Search with a Separator

Concatenate pattern + '#' + text; any Z[i] == m in the text part is a full match:

public List<Integer> search(String text, String pat) {
    String combined = pat + "#" + text;
    int m = pat.length();
    int[] z = zArray(combined);

    List<Integer> hits = new ArrayList<>();
    for (int i = m + 1; i < combined.length(); i++) {
        if (z[i] == m) {
            hits.add(i - m - 1);   // index in text
        }
    }

    return hits;
}
def search(text, pat):
    combined = pat + "#" + text
    m = len(pat)
    z = z_array(combined)

    return [i - m - 1
            for i in range(m + 1, len(combined))
            if z[i] == m]
vector<int> search(const string& text, const string& pat) {
    string combined = pat + "#" + text;
    int m = pat.size();
    vector<int> z = zArray(combined);

    vector<int> hits;
    for (int i = m + 1; i < (int)combined.size(); i++)
        if (z[i] == m)
            hits.push_back(i - m - 1);

    return hits;
}
function search(text, pat) {
  const combined = pat + "#" + text;
  const m = pat.length;
  const z = zArray(combined);

  const hits = [];
  for (let i = m + 1; i < combined.length; i++)
    if (z[i] === m) hits.push(i - m - 1);

  return hits;
}

The separator must not appear in either input — '#' is safe for lowercase text.

Pattern 3: Longest Prefix That Is Also a Suffix

Scan the Z-array of s itself — the largest Z[i] where i + Z[i] == n:

public String longestPrefixSuffix(String s) {
    int n = s.length();
    int[] z = zArray(s);

    int bestLen = 0, start = -1;

    for (int i = 1; i < n; i++) {
        if (z[i] > bestLen && i + z[i] == n) {
            bestLen = z[i];        // reaches the end → suffix
            start = i;
        }
    }

    return start == -1 ? "" : s.substring(start);
}
def longest_prefix_suffix(s):
    n = len(s)
    z = z_array(s)

    best_len, start = 0, -1

    for i in range(1, n):
        if z[i] > best_len and i + z[i] == n:
            best_len, start = z[i], i

    return "" if start == -1 else s[start:]
string longestPrefixSuffix(const string& s) {
    int n = s.size();
    vector<int> z = zArray(s);

    int bestLen = 0, start = -1;

    for (int i = 1; i < n; i++)
        if (z[i] > bestLen && i + z[i] == n) {
            bestLen = z[i];    // reaches the end → suffix
            start = i;
        }

    return start == -1 ? "" : s.substr(start);
}
function longestPrefixSuffix(s) {
  const n = s.length;
  const z = zArray(s);

  let bestLen = 0,
    start = -1;

  for (let i = 1; i < n; i++)
    if (z[i] > bestLen && i + z[i] === n) {
      bestLen = z[i]; // reaches the end → suffix
      start = i;
    }

  return start === -1 ? "" : s.slice(start);
}

Common Mistakes

Using Z[0].

By convention it’s undefined/n — loops must start at i = 1.

Wrong seed inside the box.

min(r − i, z[i − l]), not just z[i − l] — the box may end before the copied match does.

Separator that appears in the input.

'#' breaks on strings containing '#' — pick any character guaranteed absent.

Complexity

StepTimeSpace
Build Z-arrayO(n)O(n)
Search via separatorO(n + m)O(n + m)

My Private Notes

Notes are auto-saved locally to this device.