Loading…

mediumStringsSometimes asked

Pattern Search — Z-Algorithm

Q: How do you solve Pattern Search — Z-Algorithm using the Naive Z — Recompute Each Prefix Match approach?

When to use it: Mention it to define what the Z-array even is before optimizing how you fill it. The Z-array's definition is direct: for each index `i`, `z[i]` is the length of the longest substring starting at `i` that equals a prefix of the string. The naive build just realizes that definition literally. **The straightforward loop.** For every `i ≥ 1`, set a counter to 0 and compare `s[counter]` with `s[i + counter]`, incrementing while they're equal and in bounds. Store the final counter as `z[i]`. **Why it's quadratic.** Consider `s = "aaaa...a"` of length `L`. At `i = 1` you match `L − 1` characters, at `i = 2` you match `L − 2`, and so on. The total is `(L−1) + (L−2) + … ≈ L²/2`. The comparisons at different `i` overlap heavily — you keep re-confirming the same equal characters — and that overlap is exactly what the linear algorithm caches in its `[l, r]` window. **Why we don't ship it.** With `L` up to ~10⁶, `L²` is 10¹² operations. It's correct and it's a fine way to *explain* the Z-array, but it must be replaced by the windowed build for the size constraints here. Time complexity: O(L²). Space complexity: O(L).

Q: How do you solve Pattern Search — Z-Algorithm using the Windowed Z-Function (Optimal) approach?

When to use it: The answer they want. Center the explanation on the [l, r] rightmost-match window and the mirror reuse. The windowed Z-function computes the same array as the naive build but reuses prior work through a single sliding interval. **The window [l, r].** Maintain `[l, r]` as the match interval with the largest right end `r` seen so far, meaning `s[l..r]` equals the prefix `s[0..r-l]`. Initially `l = r = 0`. **Reusing the mirror.** When processing index `i`, ask: is `i` inside the current window (`i < r`)? If so, position `i` corresponds to mirror position `i - l` near the prefix, and because `s[l..r]` matches the prefix, the Z-value at the mirror `z[i-l]` applies to `i` too — *but only as far as the window extends*. So seed `z[i] = min(r - i, z[i-l])`. The `min` is the crucial cap: beyond `r` you haven't actually verified the characters, so you can't trust the mirror past that point. **Extending past the window.** After seeding, run the explicit `while` loop: while `s[z[i]] == s[i + z[i]]` and you're in bounds, increment `z[i]`. This compares only characters at or beyond `r`. If the new match `i + z[i]` reaches past the old `r`, you've discovered a farther-right verified segment, so update `l = i`, `r = i + z[i]`. **Why it's linear.** The only place real character comparisons happen is the extension loop, and every successful comparison increases `r`. Since `r` only moves rightward and never resets, the total number of successful comparisons across the whole run is bounded by `L`. Each index also does at most one failing comparison. That's `O(L)` total. **From Z-array to matches.** Build `s = p + '#' + t`. For each `i`, if `z[i] == m`, the pattern occurs in the text at index `i − (m + 1)` — subtract the pattern length `m` and the one separator character. Collect those. Time complexity: O(n + m). Space complexity: O(n + m).

Arrays & Hashing · 40 of 83 · 12 min

Given a text t of length n and a pattern p of length m, return all starting indices in t where p occurs.

Solve it with the Z-function: construct s = p + '#' + t, compute the Z-array of s, and report every index i with z[i] == m, mapped back to text coordinates. Overlapping occurrences must all be reported.

In plain English

The Z-array of a string records, at each index, how far the substring starting there agrees with the string's own prefix. If you make the pattern the prefix of a combined string, a full-length agreement (`z[i] == m`) is exactly a pattern occurrence. The challenge is computing the whole Z-array in linear time instead of O(n·m).

Examples

Example 1

Input: t = "aabxaabxcaabxaabxay", p = "aabx"
Output: [0, 4, 9, 13]
Note: s = "aabx#aabxaabxcaabxaabxay"; every position whose Z-value hits 4 maps to one of these text indices.

Example 2

Input: t = "aaaa", p = "aa"
Output: [0, 1, 2]
Note: Overlapping matches: in s = "aa#aaaa", three positions reach z == 2.

Example 3

Input: t = "abc", p = "d"
Output: []
Note: No Z-value ever reaches m = 1 for character d; empty result.

Constraints

1 ≤ m ≤ n ≤ 10⁶
There exists at least one character (the separator `#`) that appears in neither `p` nor `t`
Strings are printable ASCII unless stated otherwise
Report overlapping occurrences

Clarifying questions4First question: Can I assume a separator character exists?Explore questions

Q1.Can I assume a separator character exists?
Usually yes for ASCII text. If every byte value is in use, drop the separator idea and use KMP instead — it matches without concatenation.
Q2.Do overlapping matches count?
Yes — the Z-array naturally reports every index where the prefix-match reaches length m, including overlapping ones.
Q3.Is z[0] defined?
By convention z[0] = 0 (or the whole length); we leave it 0 because comparing the prefix with itself is not a useful match signal.
Q4.Output indices or count?
Indices in the text. Subtract m + 1 from the Z-array index to convert from combined-string coordinates.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

To find pattern `p` in text `t`, build the string `s = p + '#' + t` where `#` is a separator that appears in neither. Compute the Z-array of `s` — `z[i]` is the length of the longest substring starting at `i` that matches a prefix of `s`. Wherever `z[i] == m` (the pattern length), the pattern occurs at `i − m − 1` in the text. Building the Z-array is O(n + m) using a sliding `[l, r]` window of the rightmost match.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can avoid redundant character comparisons using the [l, r] window, and whether you pick a separator that prevents matches from crossing the pattern/text boundary.

Where candidates slip

Forgetting the separator (so the pattern's prefix bleeds into the text), or not capping the mirrored value at r − i, which over-claims unverified characters.

How to stand out

Explain the mirror reuse precisely — why z[i-l] is a valid starting guess, why it must be capped at r − i, and why r only ever moves right.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive Z — Recompute Each Prefix Match	`O(L²)`	`O(L)`	Mention it to define what the Z-array even is before optimizing how you fill it.	Read
2	Windowed Z-Function (Optimal)Optimal	`O(n + m)`	`O(n + m)`	The answer they want. Center the explanation on the [l, r] rightmost-match window and the mirror reuse.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind p in tz[i] == m ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive Z — Recompute Each Prefix Match

TimeO(L²)SpaceO(L)

Mention it to define what the Z-array even is before optimizing how you fill it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each index i, how long is the common prefix of s and the suffix starting at i? Just compare s[0], s[1], ... against s[i], s[i+1], ... until they differ.

2Hint 2Explore hint

That comparison is up to L characters per index, L = len(s). Doing it independently for every i gives L² work.

3Hint 3Explore hint

Notice you recompute overlapping comparisons many times — that's the redundancy the windowed version removes.

A · Core idea

The Z-array's definition is direct: for each index i, z[i] is the length of the longest substring starting at i that equals a prefix of the string. The naive build just realizes that definition literally.

The straightforward loop. For every i ≥ 1, set a counter to 0 and compare s[counter] with s[i + counter], incrementing while they're equal and in bounds. Store the final counter as z[i].

Why it's quadratic. Consider s = "aaaa...a" of length L. At i = 1 you match L − 1 characters, at i = 2 you match L − 2, and so on. The total is (L−1) + (L−2) + … ≈ L²/2. The comparisons at different i overlap heavily — you keep re-confirming the same equal characters — and that overlap is exactly what the linear algorithm caches in its [l, r] window.

Why we don't ship it. With L up to ~10⁶, L² is 10¹² operations. It's correct and it's a fine way to explain the Z-array, but it must be replaced by the windowed build for the size constraints here.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aabxaab"

Array state

i=4

prefix "aab" matches s[4..6]="aab" → z[4]=3

[0]

[1]

[2]

[3]

i ↓

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final resultz = [0,1,0,0,3,...]

C · Code with teaching comments

Reference implementation previewpublic class NaiveZ { public int[] zArray(String s) { int L = s.length(); int[] z = new int[L]; for (int i = 1; i < L; i++) {Explore the full code

solution.javaJava

Naive Z — Recompute Each Prefix Match — reference

2 teaching notes

1
public class NaiveZ {
2
    public int[] zArray(String s) {
3
        int L = s.length();
4
        int[] z = new int[L];
5
        for (int i = 1; i < L; i++) {
6
            int k = 0;
7
            // Compare prefix char k against the char at i+k — the literal definition of
8
            // z[i].
9
            while (i + k < L && s.charAt(k) == s.charAt(i + k)) {
10
                k++;
11
            }
12
            // k counted how far the prefix repeats starting at i.
13
            z[i] = k;
14
        }
15
        return z;
16
    }
17
 
18
    public static void main(String[] args) {
19
        int[] z = new NaiveZ().zArray("aabxaab");
20
        for (int v : z) System.out.print(v + " ");
21
        System.out.println();
22
    }
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(L²) timeO(L) spaceOpen the invariant and proofExplore the proof

Naive Z recomputes character matches that an earlier index already proved equal. The whole optimization is to remember the rightmost segment you've already verified and copy results from its mirror position.

ComplexityO(L²) time, O(L) space — L positions, each comparing up to L characters against the prefix → O(L²) where L = n + m + 1. Space O(L) for the Z-array itself.

E · Edge cases and pitfalls3Setting z[0] to L and then mistaking it for a match — keep z[0]=0 for search.Explore edge cases

Pitfalls

Setting z[0] to L and then mistaking it for a match — keep z[0]=0 for search.
Off-by-one in the bound i + k < L causing index errors.
Believing the O(L²) is acceptable at L = 10⁶.

03.2

Approach 2 of 2 · Optimal

Windowed Z-Function (Optimal)

TimeO(n + m)SpaceO(n + m)

The answer they want. Center the explanation on the [l, r] rightmost-match window and the mirror reuse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Keep a window [l, r] — the substring with the largest right endpoint r that you've already proven equals a prefix of s (so s[l..r] == s[0..r-l]).

2Hint 2Explore hint

If the current index i lies inside that window (i ≤ r), then s[i..r] mirrors s[i-l..r-l], so z[i] is at least min(r - i, z[i - l]) for free — no character comparisons needed.

3Hint 3Explore hint

After seeding z[i] from the mirror, extend it with explicit comparisons only past r. If the match reaches beyond r, slide the window to the new rightmost match.

A · Core idea

The windowed Z-function computes the same array as the naive build but reuses prior work through a single sliding interval.

The window [l, r]. Maintain [l, r] as the match interval with the largest right end r seen so far, meaning s[l..r] equals the prefix s[0..r-l]. Initially l = r = 0.

Reusing the mirror. When processing index i, ask: is i inside the current window (i < r)? If so, position i corresponds to mirror position i - l near the prefix, and because s[l..r] matches the prefix, the Z-value at the mirror z[i-l] applies to i too — but only as far as the window extends. So seed z[i] = min(r - i, z[i-l]). The min is the crucial cap: beyond r you haven't actually verified the characters, so you can't trust the mirror past that point.

Extending past the window. After seeding, run the explicit while loop: while s[z[i]] == s[i + z[i]] and you're in bounds, increment z[i]. This compares only characters at or beyond r. If the new match i + z[i] reaches past the old r, you've discovered a farther-right verified segment, so update l = i, r = i + z[i].

Why it's linear. The only place real character comparisons happen is the extension loop, and every successful comparison increases r. Since r only moves rightward and never resets, the total number of successful comparisons across the whole run is bounded by L. Each index also does at most one failing comparison. That's O(L) total.

From Z-array to matches. Build s = p + '#' + t. For each i, if z[i] == m, the pattern occurs in the text at index i − (m + 1) — subtract the pattern length m and the one separator character. Collect those.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aabxaab" (pretend p="aab", # , t="xaab" is just illustrative of Z reuse)

Array state

window l=4, r=7

i=5 inside window; mirror index = 5-4 = 1

[0]

[1]

[2]

[3]

l ↓

[4]

i ↓

[5]

[6]

Current pointerResolved stateNot processed

Final resultz = [0,1,0,0,3,1,0]

C · Code with teaching comments

solution.javaJava

Windowed Z-Function (Optimal) — optimal

6 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class ZSearch {
5
    public int[] zArray(String s) {
6
        int L = s.length();
7
        int[] z = new int[L];
8
        int l = 0, r = 0;
9
        for (int i = 1; i < L; i++) {
10
            // i sits inside the confirmed window — its mirror can seed z[i] without
11
            // comparisons.
12
            if (i < r) {
13
                // Cap the mirrored value at r-i: past r the characters are unverified,
14
                // so the mirror can't be trusted there.
15
                z[i] = Math.min(r - i, z[i - l]);
16
            }
17
            // Extend past the window; these are the only real comparisons and each one
18
            // pushes r forward.
19
            while (i + z[i] < L && s.charAt(z[i]) == s.charAt(i + z[i])) {
20
                z[i]++;
21
            }
22
            if (i + z[i] > r) {
23
                l = i;
24
                r = i + z[i];
25
            }
26
        }
27
        return z;
28
    }
29
 
30
    public List<Integer> search(String t, String p) {
31
        List<Integer> result = new ArrayList<>();
32
        int m = p.length();
33
        // Separator (control char 0x01) absent from text input prevents matches
34
        // crossing the boundary.
35
        String s = p + "\u0001" + t;
36
        int[] z = zArray(s);
37
        for (int i = m + 1; i < s.length(); i++) {
38
            if (z[i] == m) {
39
                result.add(i - (m + 1));
40
            }
41
        }
42
        return result;
43
    }
44
 
45
    public static void main(String[] args) {
46
        System.out.println(new ZSearch().search("aabxaabxcaabxaabxay", "aabx"));
47
    }
48
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.48 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proof

The window is a cache of 'the farthest-right place I've already confirmed matches the prefix'. Inside it, answers come for free from the mirror; only when you'd extend beyond the cache do you spend comparisons — and those comparisons grow the cache, so they're never wasted. That monotonic r is the whole linear-time argument.

ComplexityO(n + m) time, O(n + m) space — The explicit comparison loop only ever advances r, and r monotonically increases from 0 to at most L−1. Every character comparison either fails once (ending an extension) or pushes r forward, so the total comparisons are O(L) = O(n + m). The mirror copy is O(1) per index. Space is O(L) for the Z-array.

E · Edge cases and pitfalls7t = "aaaa", p = "aa" — s = "aa\x01aaaa"; z hits 2 at three text positions → [0,1,2].Explore edge cases

Edge cases handled

t = "aaaa", p = "aa"s = "aa\x01aaaa"; z hits 2 at three text positions → [0,1,2].
p longer than tNo z[i] reaches m → empty result, no crash.
separator already in tBug source: choose a byte guaranteed absent (here 0x01) or fall back to KMP.

Pitfalls

Dropping the separator — the prefix can match across the pattern/text boundary and over-report.
Forgetting the min(r - i, z[i-l]) cap — claims unverified characters beyond r.
Starting the extension loop from 0 instead of the seeded z[i] — silently O(L²) again.
Letting r decrease — the linear bound depends on r being monotone non-decreasing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class ZSearch { public int[] zArray(String s) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

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

public List<Integer> search(String t, String p) {
        List<Integer> result = new ArrayList<>();
        int m = p.length();
        String s = p + "\u0001" + t;
        int[] z = zArray(s);
        for (int i = m + 1; i < s.length(); i++) {
            if (z[i] == m) {
                result.add(i - (m + 1));
            }
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(new ZSearch().search("aabxaabxcaabxaabxay", "aabx"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing or unsafe separator

Without a separator that occurs in neither string, the prefix (pattern) can keep matching into the text and report false occurrences spanning the boundary.

Explore the code comparison

Don't write this

s = p + t  # pattern's prefix can run into t and over-match

Write this instead

s = p + "\x01" + t  # 0x01 appears in neither → clean boundary

Forgetting the min cap on the mirror

z[i-l] may be larger than the part of the window still ahead of i. Beyond r the characters are unverified, so copying the full mirror value claims matches you never checked.

Explore the code comparison

Don't write this

if (i < r) {
    z[i] = z[i - l];   // may exceed r - i and over-claim
}

Write this instead

if (i < r) {
    z[i] = Math.min(r - i, z[i - l]);
}

Extending from 0 instead of the seed

Re-comparing characters the mirror already guaranteed equal turns the windowed build back into the quadratic naive build.

Explore the code comparison

Don't write this

z[i] = 0
while i + z[i] < L and s[z[i]] == s[i + z[i]]:
    z[i] += 1   # ignores the free mirror result

Write this instead

if i < r:
    z[i] = min(r - i, z[i - l])
while i + z[i] < L and s[z[i]] == s[i + z[i]]:
    z[i] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Z-function: longest prefix-match starting at each index, computed with a [l,r] window

Code pattern to memorize

z[0] = 0 (by convention); l = r = 0
for i in 1..len-1:
    if i < r: z[i] = min(r - i, z[i - l])   # reuse mirror
    while i + z[i] < len and s[z[i]] == s[i + z[i]]: z[i]++   # extend
    if i + z[i] > r: l = i; r = i + z[i]   # slide window right

Rules to remember

1Concatenate p + sep + t with a separator that occurs in neither string, or a long pattern match could spill across the boundary.
2z[i] compares against the prefix of the whole concatenation, which is the pattern — that's why z[i] == m signals a hit.
3Inside the window (i < r) start from the mirror value z[i-l], but cap it at `r - i` so you never claim characters past r you haven't verified.
4Only the explicit while extension advances r; the window pointer r never moves backward, giving the linear bound.
5Map a hit back to the text: occurrence index in t is i − (m + 1) because of the pattern and the one separator character.

Use this pattern when

Exact pattern matching where you'd consider KMP but prefer prefix-based reasoning
Counting/finding all border lengths or prefix occurrences of a string
Problems framed as 'longest common prefix with the whole string at each position'
String periodicity and distinct-prefix questions

Choose another pattern when

Multiple patterns simultaneously → Aho–Corasick
Approximate matching → edit-distance DP
You can't pick a safe separator (full byte range used) → use KMP, which needs no separator
Only a yes/no existence check on tiny inputs → built-in find is enough

Interview takeaway

The Z-array answers 'how long does the prefix repeat starting here?' for every position in linear time by reusing earlier comparisons inside a sliding match window. Pattern search is just one read of that array.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternZ-Function prefix matching. Recognise it for any question phrased as 'how long does the prefix repeat starting here?' — pattern search, periodicity, borders, and distinct-prefix counting all read directly off the Z-array.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Distinct Prefix Occurrences
Coming soon
Every z[i] >= k means the length-k prefix occurs at i; aggregate to count prefix appearances.
Smallest Period via Z-Function
Coming soon
The smallest p with i + z[i] == L and i divides L gives the period.
String Compression / Borders
Coming soon
z[i] == L - i marks a border (prefix that is also a suffix).
KMP (failure-function alternative)
Same O(n+m) matching without a separator — useful when no spare character exists.

Same pattern

←

Pattern Search — KMP (Knuth–Morris–Pratt)

Continue · Next problem

Rabin–Karp Substring Search (Rolling Hash)

mediumStringsSometimes asked

Pattern Search — Z-Algorithm

Arrays & Hashing · 40 of 83 · 12 min

Given a text t of length n and a pattern p of length m, return all starting indices in t where p occurs.

In plain English

Examples

Example 1

Input: t = "aabxaabxcaabxaabxay", p = "aabx"
Output: [0, 4, 9, 13]
Note: s = "aabx#aabxaabxcaabxaabxay"; every position whose Z-value hits 4 maps to one of these text indices.

Example 2

Input: t = "aaaa", p = "aa"
Output: [0, 1, 2]
Note: Overlapping matches: in s = "aa#aaaa", three positions reach z == 2.

Example 3

Input: t = "abc", p = "d"
Output: []
Note: No Z-value ever reaches m = 1 for character d; empty result.

Constraints

1 ≤ m ≤ n ≤ 10⁶
There exists at least one character (the separator `#`) that appears in neither `p` nor `t`
Strings are printable ASCII unless stated otherwise
Report overlapping occurrences

Clarifying questions4First question: Can I assume a separator character exists?Explore questions

Q1.Can I assume a separator character exists?
Usually yes for ASCII text. If every byte value is in use, drop the separator idea and use KMP instead — it matches without concatenation.
Q2.Do overlapping matches count?
Yes — the Z-array naturally reports every index where the prefix-match reaches length m, including overlapping ones.
Q3.Is z[0] defined?
By convention z[0] = 0 (or the whole length); we leave it 0 because comparing the prefix with itself is not a useful match signal.
Q4.Output indices or count?
Indices in the text. Subtract m + 1 from the Z-array index to convert from combined-string coordinates.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can avoid redundant character comparisons using the [l, r] window, and whether you pick a separator that prevents matches from crossing the pattern/text boundary.

Where candidates slip

Forgetting the separator (so the pattern's prefix bleeds into the text), or not capping the mirrored value at r − i, which over-claims unverified characters.

How to stand out

Explain the mirror reuse precisely — why z[i-l] is a valid starting guess, why it must be capped at r − i, and why r only ever moves right.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Naive Z — Recompute Each Prefix Match	`O(L²)`	`O(L)`	Mention it to define what the Z-array even is before optimizing how you fill it.	Read
2	Windowed Z-Function (Optimal)Optimal	`O(n + m)`	`O(n + m)`	The answer they want. Center the explanation on the [l, r] rightmost-match window and the mirror reuse.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Naive Z — Recompute Each Prefix Match

TimeO(L²)SpaceO(L)

Mention it to define what the Z-array even is before optimizing how you fill it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each index i, how long is the common prefix of s and the suffix starting at i? Just compare s[0], s[1], ... against s[i], s[i+1], ... until they differ.

2Hint 2Explore hint

That comparison is up to L characters per index, L = len(s). Doing it independently for every i gives L² work.

3Hint 3Explore hint

Notice you recompute overlapping comparisons many times — that's the redundancy the windowed version removes.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aabxaab"

Array state

i=4

prefix "aab" matches s[4..6]="aab" → z[4]=3

[0]

[1]

[2]

[3]

i ↓

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final resultz = [0,1,0,0,3,...]

C · Code with teaching comments

Reference implementation previewpublic class NaiveZ { public int[] zArray(String s) { int L = s.length(); int[] z = new int[L]; for (int i = 1; i < L; i++) {Explore the full code

solution.javaJava

Naive Z — Recompute Each Prefix Match — reference

2 teaching notes

1
public class NaiveZ {
2
    public int[] zArray(String s) {
3
        int L = s.length();
4
        int[] z = new int[L];
5
        for (int i = 1; i < L; i++) {
6
            int k = 0;
7
            // Compare prefix char k against the char at i+k — the literal definition of
8
            // z[i].
9
            while (i + k < L && s.charAt(k) == s.charAt(i + k)) {
10
                k++;
11
            }
12
            // k counted how far the prefix repeats starting at i.
13
            z[i] = k;
14
        }
15
        return z;
16
    }
17
 
18
    public static void main(String[] args) {
19
        int[] z = new NaiveZ().zArray("aabxaab");
20
        for (int v : z) System.out.print(v + " ");
21
        System.out.println();
22
    }
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(L²) timeO(L) spaceOpen the invariant and proofExplore the proof

ComplexityO(L²) time, O(L) space — L positions, each comparing up to L characters against the prefix → O(L²) where L = n + m + 1. Space O(L) for the Z-array itself.

E · Edge cases and pitfalls3Setting z[0] to L and then mistaking it for a match — keep z[0]=0 for search.Explore edge cases

Pitfalls

Setting z[0] to L and then mistaking it for a match — keep z[0]=0 for search.
Off-by-one in the bound i + k < L causing index errors.
Believing the O(L²) is acceptable at L = 10⁶.

03.2

Approach 2 of 2 · Optimal

Windowed Z-Function (Optimal)

TimeO(n + m)SpaceO(n + m)

The answer they want. Center the explanation on the [l, r] rightmost-match window and the mirror reuse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Keep a window [l, r] — the substring with the largest right endpoint r that you've already proven equals a prefix of s (so s[l..r] == s[0..r-l]).

2Hint 2Explore hint

If the current index i lies inside that window (i ≤ r), then s[i..r] mirrors s[i-l..r-l], so z[i] is at least min(r - i, z[i - l]) for free — no character comparisons needed.

3Hint 3Explore hint

After seeding z[i] from the mirror, extend it with explicit comparisons only past r. If the match reaches beyond r, slide the window to the new rightmost match.

A · Core idea

The windowed Z-function computes the same array as the naive build but reuses prior work through a single sliding interval.

The window [l, r]. Maintain [l, r] as the match interval with the largest right end r seen so far, meaning s[l..r] equals the prefix s[0..r-l]. Initially l = r = 0.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aabxaab" (pretend p="aab", # , t="xaab" is just illustrative of Z reuse)

Array state

window l=4, r=7

i=5 inside window; mirror index = 5-4 = 1

[0]

[1]

[2]

[3]

l ↓

[4]

i ↓

[5]

[6]

Current pointerResolved stateNot processed

Final resultz = [0,1,0,0,3,1,0]

C · Code with teaching comments

solution.javaJava

Windowed Z-Function (Optimal) — optimal

6 teaching notes

1
import java.util.ArrayList;
2
import java.util.List;
3
 
4
public class ZSearch {
5
    public int[] zArray(String s) {
6
        int L = s.length();
7
        int[] z = new int[L];
8
        int l = 0, r = 0;
9
        for (int i = 1; i < L; i++) {
10
            // i sits inside the confirmed window — its mirror can seed z[i] without
11
            // comparisons.
12
            if (i < r) {
13
                // Cap the mirrored value at r-i: past r the characters are unverified,
14
                // so the mirror can't be trusted there.
15
                z[i] = Math.min(r - i, z[i - l]);
16
            }
17
            // Extend past the window; these are the only real comparisons and each one
18
            // pushes r forward.
19
            while (i + z[i] < L && s.charAt(z[i]) == s.charAt(i + z[i])) {
20
                z[i]++;
21
            }
22
            if (i + z[i] > r) {
23
                l = i;
24
                r = i + z[i];
25
            }
26
        }
27
        return z;
28
    }
29
 
30
    public List<Integer> search(String t, String p) {
31
        List<Integer> result = new ArrayList<>();
32
        int m = p.length();
33
        // Separator (control char 0x01) absent from text input prevents matches
34
        // crossing the boundary.
35
        String s = p + "\u0001" + t;
36
        int[] z = zArray(s);
37
        for (int i = m + 1; i < s.length(); i++) {
38
            if (z[i] == m) {
39
                result.add(i - (m + 1));
40
            }
41
        }
42
        return result;
43
    }
44
 
45
    public static void main(String[] args) {
46
        System.out.println(new ZSearch().search("aabxaabxcaabxaabxay", "aabx"));
47
    }
48
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.48 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7t = "aaaa", p = "aa" — s = "aa\x01aaaa"; z hits 2 at three text positions → [0,1,2].Explore edge cases

Edge cases handled

t = "aaaa", p = "aa"s = "aa\x01aaaa"; z hits 2 at three text positions → [0,1,2].
p longer than tNo z[i] reaches m → empty result, no crash.
separator already in tBug source: choose a byte guaranteed absent (here 0x01) or fall back to KMP.

Pitfalls

Dropping the separator — the prefix can match across the pattern/text boundary and over-report.
Forgetting the min(r - i, z[i-l]) cap — claims unverified characters beyond r.
Starting the extension loop from 0 instead of the seeded z[i] — silently O(L²) again.
Letting r decrease — the linear bound depends on r being monotone non-decreasing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.ArrayList; import java.util.List; public class ZSearch { public int[] zArray(String s) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.ArrayList;
import java.util.List;

public static void main(String[] args) {
        System.out.println(new ZSearch().search("aabxaabxcaabxaabxay", "aabx"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing or unsafe separator

Without a separator that occurs in neither string, the prefix (pattern) can keep matching into the text and report false occurrences spanning the boundary.

Explore the code comparison

Don't write this

s = p + t  # pattern's prefix can run into t and over-match

Write this instead

s = p + "\x01" + t  # 0x01 appears in neither → clean boundary

Forgetting the min cap on the mirror

z[i-l] may be larger than the part of the window still ahead of i. Beyond r the characters are unverified, so copying the full mirror value claims matches you never checked.

Explore the code comparison

Don't write this

if (i < r) {
    z[i] = z[i - l];   // may exceed r - i and over-claim
}

Write this instead

if (i < r) {
    z[i] = Math.min(r - i, z[i - l]);
}

Extending from 0 instead of the seed

Re-comparing characters the mirror already guaranteed equal turns the windowed build back into the quadratic naive build.

Explore the code comparison

Don't write this

z[i] = 0
while i + z[i] < L and s[z[i]] == s[i + z[i]]:
    z[i] += 1   # ignores the free mirror result

Write this instead

if i < r:
    z[i] = min(r - i, z[i - l])
while i + z[i] < L and s[z[i]] == s[i + z[i]]:
    z[i] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Z-function: longest prefix-match starting at each index, computed with a [l,r] window

Code pattern to memorize

z[0] = 0 (by convention); l = r = 0
for i in 1..len-1:
    if i < r: z[i] = min(r - i, z[i - l])   # reuse mirror
    while i + z[i] < len and s[z[i]] == s[i + z[i]]: z[i]++   # extend
    if i + z[i] > r: l = i; r = i + z[i]   # slide window right

Rules to remember

1Concatenate p + sep + t with a separator that occurs in neither string, or a long pattern match could spill across the boundary.
2z[i] compares against the prefix of the whole concatenation, which is the pattern — that's why z[i] == m signals a hit.
3Inside the window (i < r) start from the mirror value z[i-l], but cap it at `r - i` so you never claim characters past r you haven't verified.
4Only the explicit while extension advances r; the window pointer r never moves backward, giving the linear bound.
5Map a hit back to the text: occurrence index in t is i − (m + 1) because of the pattern and the one separator character.

Use this pattern when

Exact pattern matching where you'd consider KMP but prefer prefix-based reasoning
Counting/finding all border lengths or prefix occurrences of a string
Problems framed as 'longest common prefix with the whole string at each position'
String periodicity and distinct-prefix questions

Choose another pattern when

Multiple patterns simultaneously → Aho–Corasick
Approximate matching → edit-distance DP
You can't pick a safe separator (full byte range used) → use KMP, which needs no separator
Only a yes/no existence check on tiny inputs → built-in find is enough

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Distinct Prefix Occurrences
Coming soon
Every z[i] >= k means the length-k prefix occurs at i; aggregate to count prefix appearances.
Smallest Period via Z-Function
Coming soon
The smallest p with i + z[i] == L and i divides L gives the period.
String Compression / Borders
Coming soon
z[i] == L - i marks a border (prefix that is also a suffix).
KMP (failure-function alternative)
Same O(n+m) matching without a separator — useful when no spare character exists.

Same pattern

←

Pattern Search — KMP (Knuth–Morris–Pratt)

Continue · Next problem

Rabin–Karp Substring Search (Rolling Hash)