cf.completefrontend
STRING ALGORITHMS · ADVANCED

Z-algorithm

For every position in a string, find how many characters starting there match the start of the string, all in linear time.

Time O(n)Space O(n)3 practice problemsStep-through picture

The idea

The Z-algorithm fills an array z. For each position i, z[i] is the length of the longest piece starting at i that is also a start of the whole string. For aabxaab, z[4] is 3, because aab starting at index 4 matches the first three letters aab.

Computing each z[i] by comparing from scratch would take O(n^2) time. The algorithm keeps a box [left, right): the piece found so far, reaching furthest right, that matches the start of the string. Inside that box, the text is a copy of the string's start, so the answer at i can be read from an earlier answer, z[i - left]. Only the part past the box needs new comparisons.

To find a pattern in a text, run it on pattern + "$" + text, where $ is a character in neither. Any position in the text part with z[i] equal to the pattern's length is a match.

An everyday example

Spotting the opening line of a song

A song starts with a line, and the line comes back later, sometimes in part. You go through the lyrics and, at each word, count how many words from there match the opening. When you find a long repeat of the opening, you notice that the words inside it are a copy of the opening's words. So for a word inside that repeat, you look up the count you already wrote for the matching word near the start. You only count fresh words once you pass the end of the repeat.

How the example maps to the code
In the exampleIn the code
The opening lineThe start of text
How many words match the opening from herez[i]
The latest long repeat of the openingThe box from left to right
The matching word near the startPosition i - left
Counting fresh words past the repeatThe while loop that grows z[i]

From the slow way to z-algorithm

  1. The direct way computes each z[i] by comparing text[0], text[1], and so on with text[i], text[i + 1], and so on, until they differ. On aaaaaaaa, position i matches n - i letters, so the total is about n^2 / 2 comparisons.
  2. Many of those comparisons repeat. Suppose an earlier position left matched the start of the string up to right, so text[left..right-1] is a copy of text[0..right-left-1]. Every position inside that piece is a copy of an earlier position near the start, and that position's answer is already known.
  3. So for i inside the box, start z[i] at z[i - left], the answer at the matching spot near the start. The copy only holds up to the box's edge, so cap it at right - i. Then compare letters only past that point, because nothing past right has been checked yet.
  4. Keep the box as the match that reaches furthest right: whenever i + z[i] passes right, set left = i and right = i + z[i]. Copy, grow, move the box: that loop is the Z-algorithm.

How it works

  1. Make z with n zeros. Keep a box left and right, both 0. Characters from left up to (not including) right match the start of the string.
  2. For each i from 1: if i is inside the box (i < right), start with z[i] = Math.min(right - i, z[i - left]).
  3. Then grow z[i] while text[z[i]] === text[i + z[i]] and i + z[i] is still inside the string.
  4. If the match at i reaches past right, it becomes the new box: left = i and right = i + z[i].
  5. Set z[0] = n by convention, since the whole string matches itself. Some code leaves it at 0; say which one you use.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function zArray(text) {
  2. const n = text.length;
  3. const z = new Array(n).fill(0);
  4. let left = 0;
  5. let right = 0;
  6. for (let i = 1; i < n; i++) {
  7. if (i < right) {
  8. z[i] = Math.min(right - i, z[i - left]);
  9. }
  10. while (i + z[i] < n && text[z[i]] === text[i + z[i]]) {
  11. z[i]++;
  12. }
  13. if (i + z[i] > right) {
  14. left = i;
  15. right = i + z[i];
  16. }
  17. }
  18. if (n > 0) z[0] = n;
  19. return z;
  20. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each successful comparison moves right forward and right never moves back, so there are at most n of them. The z array has one entry per character.

  • Best caseO(n)

    No letter equals the first letter, like abcdef: each z[i] fails at its first check.

  • Average caseO(n)

    Any text: the successful comparisons are limited by how far right moves.

  • Worst caseO(n)

    One letter repeated, like aaaaaaaa: index 1 matches 7 letters, and every later index copies its answer, capped by the edge, with no new matches. That is 7 successful comparisons for 8 letters.

Common mistakes

  • Copying z[i - left] without the right - i cap. Past the box nothing is known, and the copied value can be too big.
  • Treating right as the last matching index in some lines and as one past it in others. Here the box is [left, right): right is not included.
  • Forgetting the separator when searching a pattern in a text. Without it, a match can run from the pattern part into the text part and come out longer than the pattern.
  • Assuming z[0] is the length. Some code leaves it 0; check before using it in a formula.

When to use it

Look for these clues in a problem:

  • You need, for every position, how long the match with the string's start is.
  • You want all occurrences of a pattern and can glue the pattern and text together with a separator.
  • The question is about prefixes: how often each prefix appears, or the shortest period of the string.
  • The string is long (say 10^5 characters) and comparing from every position would be too slow.

Check yourself

Answer each one in your head first, then open it.

What is the z array for abab?

[4, 0, 2, 0]. At index 2, ab matches the start; at the odd indexes, b doesn't match a.

Why must the copied value be capped at right - i?

The box only proves letters up to right. Past it, nothing has been compared with the start, so a bigger copied value could be wrong, like the 4 that would have been copied at index 6 in the trace.

Why is the separator needed for pattern search?

Without it, a match can run from the pattern part into the text part, so z[i] can be longer than the pattern, and a test for z[i] === pattern.length misses real matches.

Why does the loop start at i = 1?

z[0] is the whole string matching itself, which needs no comparisons; the code sets it to n after the loop.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each loop: z[1] to z[i - 1] are exact, and [left, right) is a piece that matches the start of the string, with right as far right as any match found so far. At i = 1, nothing is computed and the box is empty, so the rule holds.

The copy is safe. Inside the box, text[left..right-1] equals text[0..right-left-1], so the letters from i up to right equal the letters from i - left up to right - left. The match at i - left is already known, so at least Math.min(right - i, z[i - left]) letters match at i. The while loop then checks the rest one pair at a time, so z[i] ends exact.

If the copied value stops short of the box's edge, the very next check fails, because the match at i - left stopped at that same letter. So every successful comparison reads a letter at or past right, and afterwards right moves to i + z[i]. Since right never moves left and never passes n, all successful comparisons together are at most n, and each i adds at most one failed one. The loop is O(n).

Going deeper

3 more ideas

Why reading z[i - left] is correct

Inside the box, text[left..right-1] equals text[0..right-left-1]. So the letters starting at i are the same as the letters starting at i - left, at least up to the box's edge. The match at i - left was already measured, so the match at i is the same length, unless it runs into the edge. That is why the copy is capped at right - i and checked further by the while loop.

Why it is linear

Every successful comparison in the while loop pushes right further right, and right never moves left. It can only reach n, so all comparisons together are O(n). Each i also does O(1) other work. The z array uses O(n) memory.

Pattern search with a separator

Build pattern + "$" + text. The $ can't match anything, so no z value can be larger than the pattern's length. A position i past the separator with z[i] === pattern.length means the pattern starts in the text at i - pattern.length - 1.

Work it by hand

Every step in a table, with why

Fill the z array for an 8-letter text. At index 6, the copied value must be capped at the box's edge.

text = "aacaacab"

StepiBox [left, right)Startz[i]New boxWhat happensWhy
11[0, 0)01[1, 2)grow 1Outside the box, so compare from scratch: text[0] and text[1] are both a, then a and c differ.
22[1, 2)00-no match2 < 2 is false, so no copy. c doesn't match text[0], which is a.
33[1, 2)04[3, 7)grow 4aaca at index 3 matches the start aaca, then b and a differ. The new box covers indexes 3 to 6.
44[3, 7)min(3, z[1]) = 11-copy 1Index 4 is a copy of index 1, so start at z[1] = 1. One check, text[1] against text[5] (a and c), fails.
55[3, 7)min(2, z[2]) = 00-copy 0Index 5 is a copy of index 2, which had 0. One check, a against c, fails.
66[3, 7)min(1, z[3]) = 11-capped at 1Index 6 is a copy of index 3, which had z[3] = 4, but only 1 letter of room is left before right = 7. text[1] is a and text[7] is b, so z[6] really is 1.
77[3, 7)00-outside, no match7 < 7 is false, so compare from scratch: b against a fails.
80--8-z[0] = nAfter the loop, by this code's convention, the whole string matches itself.

It returns [8, 1, 0, 4, 1, 0, 1, 0]. Copying z[3] = 4 at index 6 without the cap would claim that aaca starts there, though only 2 letters are left. The while loop matched only 5 times in total.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Z-algorithmO(n)O(n)You want how much of the start matches at every position, or a pattern search that's easy to remember.
KMP pattern searchO(n + m)O(m)Pattern search with less memory, since only the pattern's table is stored.
Hashing with binary searchO(n log n)O(n)You already have prefix hashes and need the match length at only a few positions.
Compare from scratch at each positionO(n^2)O(n)Only for tiny strings, or to test the fast version.

Extra memory: O(n) for the z array. For pattern search, the joined string pattern + "$" + text and its array add O(n + m).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Z-algorithm and the other approaches, on a scale where each line up is 10 times more steps.
  • Z-algorithm O(n)
  • KMP pattern search O(n + m)
  • Hashing with binary search O(n log n)
  • Compare from scratch at each position O(n^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Z-algorithm101,0001 million
KMP pattern search202,0002 million
Hashing with binary search339,96620 million
Compare from scratch at each position1001 million1 trillion

Inputs that need care

5 tricky inputs
Empty text: ""
z is [], the loop doesn't run, and n > 0 is false, so it returns [].
One letter: "q"
The loop doesn't run, then z[0] = 1, so it returns [1].
All the same letter: "aaaa"
It returns [4, 3, 2, 1]. Index 1 does all the comparing; indexes 2 and 3 copy and are capped by right - i.
Pattern search without a separator: pattern = "ab", text "abab"
On ababab the array is [6, 0, 4, 0, 2, 0]. z[2] is 4, longer than the pattern, so a test for z[i] === 2 misses the match at text index 0. Add the separator.
A separator that also appears in the text: pattern = "a", text "a$a"
On a$a$a, z[2] is 3, because the match runs through the $. The test === 1 misses text index 0. Pick a separator that's in neither string.

Variations and follow-ups

Twists interviewers add

Pattern search

Run it on pattern + "$" + text. Any index past the separator with z[i] === pattern.length is a match starting at i - pattern.length - 1 in the text. That's O(n + m).

Smallest repeating unit

The smallest p that divides n with p + z[p] === n is the length of the unit the string repeats. For xyzxyz, z[3] = 3 and 3 + 3 = 6, so the unit is xyz.

Matches with one wrong letter

Run it forward on pattern + "$" + text, and again on both strings reversed. At each start, the forward array says how much of the pattern's start matches, and the reversed one how much of its end matches. If they cover all but one letter, it's a match with at most one mistake, in O(n + m).

Z array and KMP's table

The z array and KMP's lps table hold the same information in different shapes, and each can be built from the other in O(n). Use whichever you remember better.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "how far does the start of the string match at each position", "find all occurrences", or "is the string a repeated unit". If the answer needs comparisons with the string's own start, the z array fits.
  • Explain the box in one sentence: "inside [left, right) the text is a copy of the start, so I read z[i - left] and cap it at the edge". Then mention that real comparisons only happen past right.
  • State your convention for z[0], and say that right is not included in the box. Most bugs here are off-by-one mix-ups between those two.
  • Test by hand: one letter, all the same letter, and a case where the cap matters. The usual follow-up is pattern search: build pattern + "$" + text and look for z[i] === pattern.length.

Where frontend code uses it

The same idea in real UI code
  • Like KMP, it finds every occurrence of a search term in a document in linear time, which helps when highlighting matches in a large log viewer.
  • The z array answers "how much of this line repeats the opening?" for every position at once, which is useful for detecting repeated headers or prefixes in pasted data before importing it.

Related algorithms