✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-200

Z Algorithm for Pattern Matching

Learn how the Z Algorithm calculates prefix matches at every position in a string and uses those values for efficient pattern searching.

Explanation

Overview

The Z Algorithm is a linear-time string-processing algorithm that calculates how many characters beginning at each position match the prefix of the same string. The resulting Z array can be used to solve pattern-matching problems efficiently.

Key concepts

Prefix matching; Z array; Z-box; Prefix reuse; String preprocessing; Linear-time pattern matching

Variables

S: The input string.; Z[i]: The length of the prefix match beginning at index i.; L: The left boundary of the current Z-box.; R: The right boundary of the current Z-box.; ZBox: A substring that matches a prefix of the input string.

Complexity

zArrayConstruction: O(n) time.; patternMatching: O(n + m) time for a combined string of length n + m + 1.; space: O(n) for the Z array.

Example

inputString: AABXAAB; zArray: 0; 1; explanation: At index 4, the substring AAB matches the prefix AAB, so the Z value is 3.

Pseudocode

function ZAlgorithm(S):
n = length(S)
Z = array of size n filled with 0
L = 0
R = 0
for i = 1 to n - 1:
if i <= R:
Z[i] = min(R - i + 1, Z[i - L])
while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
Z[i] += 1
if i + Z[i] - 1 > R:
L = i
R = i + Z[i] - 1
return Z

Applications

Pattern searching.; Prefix matching.; Repeated substring analysis.; String periodicity problems.; Competitive programming.

Variables

S

The input string.

Z[i]

The length of the prefix match beginning at index i.

L

The left boundary of the current Z-box.

R

The right boundary of the current Z-box.

ZBox

A substring that matches a prefix of the input string.

Example or application

Input String

AABXAAB

Z Array

  • 0

  • 1

  • 0

  • 0

  • 3

  • 1

  • 0

Explanation

At index 4, the substring AAB matches the prefix AAB, so the Z value is 3.

Definition

The Z Algorithm is a linear-time string-processing algorithm that calculates how many characters beginning at each position match the prefix of the same string. The resulting Z array can be used to solve pattern-matching problems efficiently.

Mathematical Representation

Z[i] = the length of the longest substring starting at position i that matches a prefix of the complete string. Conventionally, Z[0] is set to 0.

Pattern Matching Method

Combined String

pattern + separator + text

Separator

A character that does not occur in either the pattern or the text.

Matching Condition

If a Z value equals the pattern length, the pattern occurs at the corresponding text position.

Algorithm Steps

  • Initialize the Z array with zeros.

  • Maintain the boundaries of the current matching Z-box.

  • For each position, reuse previously known matching information when the position lies inside the current Z-box.

  • Compare additional characters while they match the prefix.

  • Update the Z-box boundaries when a longer match is discovered.

  • For pattern searching, construct a combined string containing the pattern, a unique separator, and the text.

  • Find positions where the Z value equals the pattern length.

Pseudocode

function ZAlgorithm(S):
n = length(S)
Z = array of size n filled with 0
L = 0
R = 0
for i = 1 to n - 1:
if i <= R:
Z[i] = min(R - i + 1, Z[i - L])
while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
Z[i] += 1
if i + Z[i] - 1 > R:
L = i
R = i + Z[i] - 1
return Z

Complexity

Z Array Construction

O(n) time.

Pattern Matching

O(n + m) time for a combined string of length n + m + 1.

Space

O(n) for the Z array.

Key Concepts

  • Prefix matching

  • Z array

  • Z-box

  • Prefix reuse

  • String preprocessing

  • Linear-time pattern matching

Advantages

  • Builds the Z array in linear time.

  • Can be used for exact pattern matching.

  • Provides useful information about repeated prefixes.

  • Uses previously calculated matching regions to avoid unnecessary comparisons.

Limitations

  • The Z-box concept may be difficult for beginners to understand.

  • The combined-string method requires a separator that cannot appear in the pattern or text.

  • The algorithm computes prefix-match lengths rather than directly storing all possible substring relationships.

Applications

  • Pattern searching.

  • Prefix matching.

  • Repeated substring analysis.

  • String periodicity problems.

  • Competitive programming.

Related Topics

  • KMP Algorithm

  • Longest Prefix-Suffix Array

  • String Algorithms

  • Pattern Matching

Practice Question

What does Z[i] represent in the Z Algorithm?

Practice Answer

The length of the longest substring starting at index i that matches a prefix of the entire string.

Learning Objectives

  • Explain the central idea and purpose of z algorithm for pattern matching.

  • Identify the assumptions, inputs, and conditions relevant to z algorithm for pattern matching.

  • Evaluate an application of z algorithm for pattern matching for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • String Algorithms and Pattern Matching

Suggest a correction or source · More in Algorithms & Data Structures