CoreSource checked

Z Algorithm

Computes how much each string suffix matches the string prefix.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Linear String Preprocessing
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: Z-Function

Overview

The Z Algorithm builds a Z-array that can be used for fast exact pattern matching and string analysis.

Core Concepts

pattern comparisonstring sequencelinear string preprocessingsequence scanpattern statematch verification

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

When to Use

Use Z Algorithm when you need to maintain a matching window.
Use it for exact string search with inputs like string or pattern-text combination.
Use it when exact, fuzzy, or structured patterns must be found in sequences.
Use it when the Linear String Preprocessing tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when preprocessing cost is larger than a one-off simple scan.
Avoid it when the required output is not z-array.

What It Does

Maintains a matching window
Computes prefix-match lengths for each position

Use Cases

Exact string search
String periodicity checks
Pattern preprocessing

Inputs

String or pattern-text combination

Outputs

Z-array
Optional match positions

Key Formulas (1)

Z value

Z_[i] = longest prefix length matching string_[i…]

Z[i] = longest prefix length matching string[i...]

Stores how far the string prefix matches from each position.

Pseudocode

1.Keep the current rightmost match window
2.For each position, reuse known overlap when possible
3.Extend the match by direct comparison
4.Update the rightmost window
5.Use full pattern-length entries as matches

Canonical Example

Input: text = 'abracadabra', pattern = 'abra'
Output: matches at positions [0, 7]
Explanation: Z Algorithm: The algorithm scans the sequence and reports where the pattern appears.

Implementation Notes

Keep the input contract explicit: String or pattern-text combination.
Use this step as the implementation spine: Keep the current rightmost match window.
Then preserve the next state change: For each position, reuse known overlap when possible.
Decide whether indexes mean bytes, code units, characters, or tokens.
Test overlapping matches, empty patterns, repeated characters, and no-match inputs.

Common Pitfalls

The Z-array is often simpler to reason about than failure functions for some tasks.
Indexing by bytes instead of characters can break text with multibyte characters.
Reporting a match before verifying collisions, boundaries, or full-pattern alignment.
Returning z-array without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show a prefix match window reused across string positions.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Keep the current rightmost match window

z-box

Notes

Z Algorithm operates in O(n) time and O(n) space within the Linear String Preprocessing family. Key governing relation: Z[i] = longest prefix length matching string[i...]. Often compared with Knuth-Morris-Pratt and Suffix Array Search.