An Introduction to Knuth-Morris-Pratt Algorithm

DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

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.

Historical Background and Significance

Donald Knuth, Vaughan Pratt, and James H. Morris first presented the KMP algorithm in 1970. Their main achievement was to enhance the performance of an extraordinarily important issue in computer science called pattern matching. Before KMP, most pattern-matching algorithms used took up to quadratic time, which made their use in large texts almost impossible.

 

The importance or the value of the KMP algorithm is that it only requires O(n + m) time to work with it; n is the number of characters in the text, while m represents the number of characters in the pattern. This pioneering accomplishment was to give a highly effective procedure for string matching issues.

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 ReadWhat 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.

 

Step-by-Step Breakdown of the KMP Algorithm

Understanding the Knuth-Morris-Pratt algorithm involves two main phases: preprocessing the pattern and performing the pattern matching. Let’s walk through each step to see how these phases work together to efficiently search for a pattern within a text.

 

Phase 1: Preprocessing the Pattern

 

The first step is to preprocess the pattern to create the Longest Prefix Suffix (LPS) array. This array helps us skip unnecessary comparisons during the pattern-matching phase.

 

  1. Initialise Variables: Start with two variables. i will iterate over the pattern, and len will keep track of the current longest prefix, which is also a suffix.
  2. Create the LPS Array: Initialise an array lps of the same length as the pattern, with all values set to 0. Set the first value, lps[0], to 0 because a single character has no proper prefix or suffix.
  3. Iterate Through the Pattern: Move through the pattern using the following logic:
    • If the characters at positions i and len match, increment both i and len, and set lps[i] = len.
    • If the characters do not match and len is not 0, set len to lps[len-1] and do not increment i.
    • If len is 0, set lps[i] = 0 and increment i.

 

Example of LPS Array Construction

 

Consider the pattern “ABABAC”:

 

  1. Initialise i = 1 and len = 0. The LPS array starts as [0, 0, 0, 0, 0, 0].
  2. Compare pattern[0] (‘A’) with pattern[1] (‘B’). They don’t match, so set lps[1] = 0 and increment i to 2.
  3. Compare pattern[0] (‘A’) with pattern[2] (‘A’). They match, so set lps[2] = 1, increment len to 1, and i to 3.
  4. Compare pattern[1] (‘B’) with pattern[3] (‘B’). They match, so set lps[3] = 2, increment len to 2, and i to 4.
  5. Compare pattern[2] (‘A’) with pattern[4] (‘A’). They match, so set lps[4] = 3, increment len to 3, and i to 5.
  6. Compare pattern[3] (‘B’) with pattern[5] (‘C’). They don’t match, so set len to lps[2] = 1 and compare again. They don’t match; set len to lps[0] = 0. Set lps[5] = 0 and increment i to 6.

 

The final LPS array for “ABABAC” is [0, 0, 1, 2, 3, 0].

Phase 2: Pattern Matching

 

Once we have the LPS array, we can proceed with the pattern-matching phase. This phase involves using the LPS array to avoid unnecessary comparisons.

 

  1. Initialise Variables: Use two pointers, i for the text and j for the pattern. Start both at 0.
  2. Compare Characters:
    • If the characters at text[i] and pattern[j] match, increment both i and j.
    • If j equals the length of the pattern, we have found a match. Record the position, and reset j using lps[j-1].
    • If the characters do not match and j is not 0, set j to lps[j-1]. If j is 0, increment i.

 

Example of Pattern Matching

 

Let’s match the pattern “ABABAC” in the text “ABABABAC”:

 

  1. Initialise i = 0 and j = 0.
  2. Compare text[0] (‘A’) with pattern[0] (‘A’). They match, increment i and j.
  3. Continue matching until i = 6 and j = 5. Text[6] (‘C’) matches pattern[5] (‘C’). Increment both i and j.
  4. j equals the length of the pattern, so we found a match at index i – j = 0.
  5. Reset j to lps[5] = 0 and continue.

 

We find the pattern “ABABAC” starting at index 0 in the text “ABABABAC”.

DevOps & Cloud Engineering
Internship Assurance
DevOps & Cloud Engineering

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:

 

// Java program for implementation of KMP (Knuth-Morris-Pratt) pattern matching 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

Real-World Applications of the KMP Algorithm

The Knuth-Morris-Pratt algorithm is used in various real-world applications where efficient pattern matching is crucial. Its ability to locate patterns quickly within text makes it an invaluable tool in many fields. Let’s explore some of the key areas where the KMP algorithm proves useful.

 

Plagiarism Detection

 

One of the primary applications of the KMP algorithm is in plagiarism detection. Educational institutions and content creators need reliable tools to identify copied content. The KMP algorithm scans documents to find exact matches of specific phrases or sentences, ensuring originality in academic and creative works.

 

DNA Sequencing

 

In bioinformatics, DNA sequencing involves identifying specific sequences within a genome. The KMP algorithm’s efficiency makes it suitable for searching large DNA sequences for specific patterns. This capability is vital for genetic research, disease identification, and understanding genetic variations.

 

Digital Forensics

 

Digital forensics experts use the KMP algorithm to search for specific patterns in digital evidence. Whether identifying malicious code within the software or finding specific text in a large dataset, the KMP algorithm helps forensic analysts quickly locate the information they need.

 

Text Editors and Search Engines

 

Text editors and search engines rely on efficient pattern-matching algorithms to provide quick search results. The KMP algorithm enables these tools to highlight occurrences of search terms within documents, web pages, or databases. This ensures users get accurate and fast results.

 

Intrusion Detection Systems

 

In cybersecurity, intrusion detection systems (IDS) monitor network traffic for suspicious patterns. The KMP algorithm helps these systems to identify known attack signatures within the network data. This early detection is crucial for preventing security breaches.

 

Advantages and Disadvantages of the KMP Algorithm

Advantages

 

  • Efficiency: The Knuth-Morris-Pratt algorithm has a linear time complexity, O(n + m). This efficiency makes it suitable for large texts and patterns.
  • No Redundant Comparisons: The algorithm avoids unnecessary comparisons by using the LPS array, speeding up the search process.
  • Versatility: The KMP algorithm can be adapted for various applications, from text search to DNA sequencing.

Disadvantages

 

  • Complexity: The KMP algorithm can be difficult to understand and implement, especially for beginners.
  • Preprocessing Overhead: Although the LPS array significantly improves efficiency, the preprocessing step adds overhead, which might not be ideal for very short patterns or texts.

Also Read – Arrays in Data Structure: Types & Applications

Conclusion

Of the various possible methods of pattern matching, the Knuth-Morris-Pratt algorithm proves to be one of the most important. In this blog, we have discussed the complexities of the algorithm, from its history to its basic and advanced workings and numerous uses. String matching with the help of the KMP algorithm differs from the basic one, as it employs the LPS array, which makes the searching process more efficient by not performing unnecessary comparisons.

 

We learned that the KMP algorithm’s time complexity is O(n + m), and it is ideal for large texts and patterns, especially compared to other naive methods. It can be used in many fields, such as plagiarism checking, DNA assemblers, digital investigation, text editors, search engines, and cyber security systems. This aspect makes it essential in learning institutions and other workplaces or organisations.

The KMP algorithm has many benefits, even though computers may find it somewhat tough to handle. When dealing with pattern-matching tasks, knowledge and application of the LPS array can greatly improve the way in which these strategies are carried out. Not only does the algorithm enhance the speeds of searches, but it is also a stable starting point for numerous problems regarding text analysis.

 

 

FAQs
The Knuth-Morris-Pratt algorithm reduces the number of unnecessary comparisons by employing the LPS array, rendering it linear in time complexity. This efficiency is especially important in dealing with large texts and patterns.
The LPS array helps avoid futile comparisons by storing the length of the longest prefix, which is also the suffix of the pattern. This helps the algorithm exclude characters that have already been matched, thereby saving computation time.
Yes, the Knuth-Morris-Pratt algorithm can be modified to allow for extended matches and thus perform multiple pattern searches. However, each pattern will require its own LPS array, which will be easier to make and use separately in this case.
The KMP algorithm is applied in areas like plagiarism checks, DNA barcoding, text editors, search engines, digital forensics, and intrusion detection systems. Due to its efficiency, it finds its use in many different fields where fast and accurate pattern recognition is needed.
One of the KMP algorithm's limitations is the difficulty inherent in comprehending how the LPS array is built and used due to the increased levels of constructiveness introduced. This complicates the task due to the necessity of preprocessing the pattern and handling the array within the matching phase.

Book a free counselling session

India_flag

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

left dot patternright dot pattern

Programs tailored for your Success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles
View all
Hero Vired logo
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies

Certificate Program in Financial Analysis, Valuation and Risk Management

Management

Certificate Program in Strategic Management and Business Essentials

Executive Program in Product Management

Certificate Program in Product Management

Certificate Program in Technology-enabled Sales

Future Tech

Certificate Program in Gaming & Esports

Certificate Program in Extended Reality (VR+AR)

Professional Diploma in UX Design

Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved