Efficient Pattern Searching: Z-Algorithm & KMP

Hello! In our previous lesson, we explored a specialized counting pattern for sliding windows. We've now covered a variety of string manipulation and searching techniques, from basic operations to sophisticated window-based approaches.

Today, we address one of the most fundamental problems in computer science: finding all occurrences of a smaller pattern string within a larger text string. We will move beyond the simple sliding window and learn about highly optimized, linear-time algorithms designed specifically for this task. Your learning outcome is to implement either the Z-algorithm or the KMP algorithm. We will explore both, as they represent two powerful and elegant solutions that are mainstays of competitive programming and technical interviews.

1. The Challenge of Pattern Searching

Imagine searching for a specific DNA sequence in a genome, or using Ctrl+F in a massive document. This is pattern searching. The most straightforward way to do this is to check every possible starting position in the text and see if the pattern matches from there.

Let's formalize this.

InterviewBit KMP Algorithm for Pattern Searching - InterviewBit

This article from InterviewBit starts by clearly defining the problem and presenting the brute-force solution, which is our essential starting point.

First, read the Problem Statement to understand the task. Then, review the Naive Approach section. Focus on the steps of the algorithm and the corresponding Java Implementation.

This naive approach involves two nested loops. The outer loop iterates through possible starting positions in the text (from 0 to N-M), and the inner loop checks for a character-by-character match of the pattern. In the worst-case scenario (e.g., text ="aaaa...ab" and pattern ="aaab"), we perform M comparisons for almost every one of the N-M+1 starting positions. This results in a time complexity of O(N * M), which is too slow for large inputs.

The core inefficiency is that when a mismatch occurs, the naive algorithm throws away all the information it gained. For example, if we match 7 characters of a pattern and fail on the 8th, we simply shift the window by one and start comparing from scratch. The genius of algorithms like KMP and Z-algorithm lies in reusing the information from a partial match to make much larger, "smarter" shifts.

2. The Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm achieves a linear time complexity of O(N + M) by cleverly preprocessing the pattern. This preprocessing creates a helper array, often called lps (Longest Proper Prefix which is also a Suffix), that allows the algorithm to avoid redundant comparisons in the text.

The Core Idea: The `lps` Array

The lps array is the heart of KMP. For each position i in the pattern, lps[i] stores the length of the longest proper prefix of the substring pattern[0...i] that is also a suffix of that same substring.

A proper prefix is a prefix that is not the entire string itself.
A suffix is a sequence of characters at the end of a string.

Let's take the pattern P = "ababc":

lps[0] (a): No proper prefixes. lps[0] = 0.
lps[1] (ab): Proper prefixes are a. Suffixes are b. No match. lps[1] = 0.
lps[2] (aba): Proper prefixes are a, ab. Suffixes are a, ba. The longest match is a. Length is 1. lps[2] = 1.
lps[3] (abab): Proper prefixes: a, ab, aba. Suffixes: b, ab, bab. Longest match is ab. Length is 2. lps[3] = 2.
lps[4] (ababc): No proper prefix is also a suffix. lps[4] = 0.

So, for P = "ababc", the lps array would be [0, 0, 1, 2, 0].

How KMP Uses the `lps` Array

Now, how does this help? Let's say we are matching a text T against this pattern P. We use two pointers, i for the text and j for the pattern.

Initial setup for a KMP search. Pointers `i` (for the text) and `j` (for the pattern) start at index 0. The `lps` array for the pattern is pre-computed.

We advance i and j as long as characters match. Suppose a mismatch occurs at T[i] and P[j]. This means P[0...j-1] successfully matched T[i-j...i-1].

Instead of just shifting the pattern by one, we consult lps[j-1]. The value len = lps[j-1] tells us that the prefix P[0...len-1] is identical to the suffix P[j-len...j-1]. Since P[0...j-1] just matched a part of the text, we already know that P[0...len-1] will match the text segment right before the mismatch position i. We can therefore "slide" the pattern forward and resume our comparison from P[len], without backtracking the text pointer i.

This image shows how KMP handles a mismatch. After matching 6 characters of the pattern `kaykayak`, a mismatch occurs. We look at the `lps` value for the previous character (`lps[5] = 3`). This tells us there's a prefix of length 3 (`kay`) that matches the suffix of the matched part. We can shift the pattern so this prefix aligns, and resume comparing from index 3 of the pattern, avoiding re-comparisons.

The following video provides an excellent visual walkthrough of how the lps array is constructed and used during the search.

Knuth Morris Pratt (KMP) String Search Algorithm - tutorial with failure function in Java

This tutorial from Stable Sort clearly explains the KMP algorithm's intuition and mechanics.

Watch the introduction here to understand the fundamental question KMP asks: how can we shift by more than one position after a mismatch? Next, focus on the explanation of the lps array (called the prefix length array or failure function) from this segment. This is the most crucial part of understanding the "why". Finally, see the algorithm in action in the example walkthrough, which demonstrates how the lps array guides the pattern shifts.

KMP Implementation

Now, let's look at the code. The implementation consists of two parts: a function to compute the lps array, and the main search function that uses it.

InterviewBit KMP Algorithm for Pattern Searching - InterviewBit

The InterviewBit article provides a complete Java implementation that aligns perfectly with our discussion.

First, read the conceptual overview in the section KMP Pattern Searching. Next, carefully study the Java Implementation of KMP. Pay close attention to the two distinct functions: computeLPSArray and KMPStringSearch. Trace how the j = lps[j-1] logic is applied on a mismatch. Finally, review the Complexity Analysis. It's O(N+M) because both the lps computation and the search phase process each character a constant number of times.

3. The Z-Algorithm

The Z-algorithm is another brilliant linear-time pattern searching method. Its approach is different from KMP but equally effective. It's often favored in competitive programming for its slightly more straightforward implementation once the core concept is understood.

The Core Idea: The Z-Array

The Z-algorithm revolves around computing a Z-array. For a given string S of length n, the Z-array Z is also of length n. For each index i (from 1 to n-1), Z[i] is defined as the length of the longest substring starting from S[i] that is also a prefix of S. Z[0] is conventionally set to 0.

Example: S = "aabaacaa"

Z[0] = 0 (by definition)
Z[1] (a...): The substring starting at index 1 is "abaacaa". Its longest common prefix with S is "a". Length = 1. Z[1] = 1.
Z[2] (b...): No prefix match. Z[2] = 0.
Z[3] (a...): The substring is "aacaa". Longest common prefix with S is "aa". Length = 2. Z[3] = 2.
... and so on. The full Z-array is [0, 1, 0, 2, 1, 0, 2, 1].

How the Z-Algorithm is Used for Pattern Searching

The trick is to apply the Z-array to a specially constructed string.

Create a new string: new_S = pattern + "$" + text, where $ is a separator character not found in either string.
Compute the Z-array for new_S.
Now, iterate through the Z-array. Any index i where Z[i] is equal to the length of the pattern signifies an occurrence of the pattern in the text! Why? Because it means a substring of length pattern.length() starting at i in new_S is also a prefix of new_S (and the prefix of new_S is the pattern itself).
The final step is to map the index i from new_S back to an index in the original text. This is simply i - pattern.length() - 1.

Z Algorithm Z values

Tushar Roy provides one of the clearest explanations of the Z-algorithm available.

First, watch the segment defining the Z-array and how to calculate it naively for a sample string. Next, see how this concept is applied to pattern matching from this walkthrough. It shows the pattern + $ + text construction and how to find matches.

The Linear-Time Optimization (The "Z-Box")

Just like with KMP, the naive way to compute the Z-array would be O(N^2). The linear-time optimization maintains a "Z-box" [L, R], which represents the boundaries of the rightmost substring found so far that is also a prefix. When calculating Z[i], if i is inside this box, we can use previously computed Z-values to avoid re-comparing characters we've already seen.

This part is conceptually dense but is the key to the algorithm's efficiency. The resources below walk through the implementation in detail.

Z Function - Tutorial

The "takeuforward" tutorial, part of your preferred DSA sheet, provides a complete guide with Java code.

Read the motivation and the high-level steps under the Algorithm heading. Study the Java implementation carefully. The computeZArray function contains the optimized "Z-box" logic. Trace how the left and right pointers are used to avoid redundant work. The zFunctionSearch function shows how it's all put together. Finally, review the complexity analysis to confirm the linear time and space performance.

Conclusion

You have just learned two of the most powerful algorithms for string pattern matching. While they work differently, both KMP and the Z-algorithm achieve the optimal linear time complexity by cleverly reusing information from partial matches to avoid redundant work.

Key Takeaways:

Naive Pattern Search: Simple to implement but inefficient at O(N * M) due to redundant comparisons.
KMP Algorithm: Preprocesses the pattern to build an lps array. This array helps make intelligent jumps in the pattern on a mismatch, avoiding backtracking in the text. Its complexity is O(N + M).
Z-Algorithm: Preprocesses a combined string (pattern + $ + text) to build a Z-array. Occurrences are found where the Z-value equals the pattern length. It also runs in O(N + M).
Core Principle: The key to both algorithms is amortization. While a single comparison might trigger a series of operations, over the entire execution, each character in the text and pattern is examined only a constant number of times.

For interviews, KMP is arguably more famous, but the Z-algorithm is a fantastic tool to have. Understanding the core idea of one of them deeply is essential.

This lesson concludes our module on Strings. We are now ready to pivot from linear data structures like arrays and strings to more complex, non-linear structures. In our next lesson, we will begin our journey into Linked Lists, starting with the fundamentals of implementing a singly linked list in Java.

Recommended resources