An Introduction to Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt algorithm can be regarded as a major contribution to the analysis of string match problems. It involves seeking a given sequence of characters or patterns within a larger text. Hence, the traditional search methods, such as the naive approach, often lead to slow, inefficient searches, particularly when searching through long texts. KMP (algorithm developed by Donald Knuth, Vaughan Pratt, and James H. Morris in 1970.) The running time of this algorithm is linear. This efficiency is made through intelligent pattern preprocessing, which determines the need for certain comparisons.

String matching is not just a theoretical concept but a practical necessity in various fields. From search engines to DNA sequence comparisons and text editors, the KMP algorithm’s efficiency makes it a valuable tool in these and many other domains, underscoring its relevance and versatility.

Detailed Explanation of the Knuth-Morris-Pratt Algorithm

Basic Principles

The KMP algorithm is a significant improvement over naive methods, as it avoids redundant comparisons. Instead of checking every possible starting position in the text, KMP preprocesses the pattern to build an auxiliary array known as the Longest Prefix Suffix (LPS) array. This array is the key to the algorithm’s efficiency. It helps in skipping characters that we know will match, thus reducing the number of comparisons needed and ultimately speeding up the search process.

How It Works

The KMP algorithm operates in two main phases:

1. Preprocessing the Pattern: This involves constructing the LPS array, which stores the lengths of the longest prefix, which is also a suffix for each sub-pattern.
2. Pattern Matching: Using the LPS array, the algorithm scans the text to find the pattern efficiently.

The key idea is that when a mismatch occurs after some matches, the LPS array indicates the next positions to match, thereby skipping unnecessary checks.

Why It’s Efficient

The efficiency of the KMP algorithm comes from its ability to avoid backtracking in the text. By using the LPS array, the algorithm ensures that each character of the text is compared at most once. This results in a linear time complexity, making it significantly faster than traditional methods.

Also Read– What is Data Structure

The Role and Construction of the Longest Prefix Suffix (LPS) Array

Importance of the LPS Array

The LPS array is central to the KMP algorithm. It helps optimise the search process by indicating the longest proper prefix of the pattern, which is also a suffix. This information allows the algorithm to skip unnecessary comparisons and resume matching from the correct position.

How to Construct the LPS Array?

We compute the LPS values for each pattern point as part of the preprocessing procedure before building the LPS array. The following is a detailed explanation:

1. Initialisation: Start with an array lps of the same length as the pattern, initialised to 0. The first element of the LPS array is always 0 since a single character cannot have a proper prefix or suffix.
2. Iterate Over the Pattern: Use two pointers, i and len, where i traverses the pattern, and len tracks the length of the current longest prefix suffix.
3. Matching Characters:
   • If the characters at positions i and len match, increment len and set lps[i] = len. Move i to the next position.
   • If the characters do not match and len is not 0, set len to lps[len-1]. This step avoids unnecessary comparisons by using previously computed LPS values.
   • If len is 0, set lps[i] = 0 and move i to the next position.

Here’s a simple example to illustrate the process:

Example

Consider the pattern “ABABAC”:

1. Start with i = 1 and len = 0.
2. A (pattern[0]) matches A (pattern[1]), so set lps[1] = 1 and increment i and len.
3. B (pattern[1]) matches B (pattern[2]), so set lps[2] = 2 and increment i and len.
4. Continue this process until i = 5. If a mismatch occurs, adjust len using lps[len-1] and continue.

By the end of this process, we have the LPS array: [0, 0, 1, 2, 3, 0].

Practical Implications

The LPS array is crucial for the efficiency of the KMP algorithm. It ensures the algorithm skips unnecessary comparisons, making the pattern-matching process faster and more efficient. Although this preprocessing step takes linear time, it significantly enhances the overall performance of the KMP algorithm.

Time Complexity and Efficiency Analysis

The Knuth-Morris-Pratt algorithm is efficient because it processes the text and the pattern in linear time, O(n + m). This efficiency stems from the preprocessing phase, where we build the LPS array in O(m) time, and the matching phase, where each character in the text is compared at most once, resulting in O(n) time.

Comparison with the Naive Approach

In contrast, the naive pattern-matching approach can take up to O(n * m) time in the worst case. This inefficiency arises because it checks every possible starting position in the text, leading to many redundant comparisons.

Why KMP is Better

The KMP algorithm’s use of the LPS array allows it to skip portions of the text that have already been matched. This reduces the number of comparisons, making the algorithm faster and more efficient, especially for long texts and patterns.

Practical Examples and Code Implementations

Example 1: Matching DNA Sequences

Let’s consider a practical example of matching DNA sequences. Suppose we want to find the sequence “AGCT” in a long DNA string “AGCTTAGCTGAGCTAGCT”:

1. Preprocess the pattern “AGCT” to create the LPS array [0, 0, 0, 0].
2. Use the KMP algorithm to match the pattern in the text. We find matches at positions 0, 7, and 13.

Example 2: Searching in a Text File

Another practical use of the KMP algorithm is searching for a specific word in a large text file. Let’s search for the word “algorithm” in a document:

1. Preprocess the pattern “algorithm” to create the LPS array.
2. Use the KMP algorithm to find all occurrences of the word in the document.

Code Implementation in Java

Below is a Java implementation of the KMP algorithm:

public class KMPAlgorithm {

// Method to perform the KMP search algorithm

void searchPattern(String pattern, String text) {

int patternLength = pattern.length();

int textLength = text.length();

// Create lps array that will hold the longest prefix suffix values for pattern

int[] lps = new int[patternLength];

int patternIndex = 0; // index for pattern

// Preprocess the pattern (calculate lps array)

computeLPSArray(pattern, patternLength, lps);

int textIndex = 0; // index for text

while ((textLength – textIndex) >= (patternLength – patternIndex)) {

if (pattern.charAt(patternIndex) == text.charAt(textIndex)) {

patternIndex++;

textIndex++;

}

if (patternIndex == patternLength) {

System.out.println(“Pattern found at index ” + (textIndex – patternIndex));

patternIndex = lps[patternIndex – 1];

} else if (textIndex < textLength && pattern.charAt(patternIndex) != text.charAt(textIndex)) {

if (patternIndex != 0) {

patternIndex = lps[patternIndex – 1];

} else {

textIndex++;

}

}

}

}

// Method to compute the longest prefix suffix array

void computeLPSArray(String pattern, int patternLength, int[] lps) {

int length = 0; // length of the previous longest prefix suffix

int i = 1;

lps[0] = 0; // lps[0] is always 0

// Loop to calculate lps[i] for i = 1 to patternLength – 1

while (i < patternLength) {

if (pattern.charAt(i) == pattern.charAt(length)) {

length++;

lps[i] = length;

i++;

} else {

if (length != 0) {

length = lps[length – 1];

} else {

lps[i] = length;

i++;

}

}

}

}

// Main method for testing the KMP search algorithm

public static void main(String[] args) {

String text = “TESTTEXTFORPATTERNMATCHING”;

String pattern = “PATTERN”;

new KMPAlgorithm().searchPattern(pattern, text);

}

}

Output