concept · INFO-CS-ADS-200Z 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
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
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.
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.
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