Z-Algorithm — Linear Pattern Matching

What does it solve?

The Z-array of a string gives, for every index i, the length of the longest substring starting at i that is also a prefix of the whole string. To find a pattern, build the Z-array of P + separator + T.

Key insight: maintain the rightmost Z-box [L, R], the interval matching a prefix that extends furthest right. Inside the box, reuse the already-known Z-value of the mirror index instead of recomputing. Wherever Z[i] == |P| in the search phase, the pattern occurs. Everything is O(N + M).

The core idea

// [L,R] = rightmost Z-box
for i = 1..n-1:
  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]++
  if i+z[i] > R: L=i, R=i+z[i]

Complexity

Time complexity

O(N + M)

The R pointer only ever moves forward across the concatenated string, so the total work of the inner while-loop is linear.

Space complexity

O(N + M)

One Z-value per character of the concatenation P + separator + T. No other structures scale with the input.

Examples & edge cases

Live animation — build the Z-array of P + $ + T

prefix reference current index i Z-box [L,R] characters matching separator $

Press Play to start

Concatenation P $ T

Current step detail

i = — L = — R = — matches = —

Step — of —

index i

—

position in concat

Z[i]

—

prefix length

Z-box R

—

rightmost reach

matches found

—

where Z[i]=|P|

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	Case	L	R	Z[i]	Action	Match?

C++ implementation

z_algorithm.cpp

#include <bits/stdc++.h>
using namespace std;

// Z[i] = length of the longest substring from i that is also a prefix of s
vector<int> zArray(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;                          // whole string is its own prefix
    int L = 0, R = 0;                 // rightmost Z-box
    for (int i = 1; i < n; i++) {
        if (i < R)
            z[i] = min(R - i, z[i - L]);   // reuse the mirror value
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;                        // extend by explicit comparison
        if (i + z[i] > R) {                 // grew the box → update [L,R]
            L = i;
            R = i + z[i];
        }
    }
    return z;
}

// Find all occurrences of p in t using P + '$' + T
vector<int> zSearch(const string& t, const string& p) {
    string s = p + "$" + t;
    auto z = zArray(s);
    vector<int> res;
    int m = p.size();
    for (int i = m + 1; i < (int)s.size(); i++)
        if (z[i] == m) res.push_back(i - m - 1); // map back to t
    return res;
}

int main() {
    auto hits = zSearch("ABABAAB", "ABA");
    for (int x : hits) cout << x << " "; // 0 2
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars