Skip to main content

Knuth-Morris-Pratt (KMP) Algorithm

Problem Statement​

Problem Description​

The Knuth-Morris-Pratt (KMP) algorithm is an efficient string searching algorithm that improves the performance of substring searches within a main string. The algorithm preprocesses the pattern to create a partial match table (also known as the "lps" array), which is used to skip unnecessary comparisons during the search process.

Examples​

Example 1:

Input: 
Text: "abxabcabcaby"
Pattern: "abcaby"
Output: 
Pattern found at index 6

Constraints​

  • The length of the text and the pattern can be up to 10^5.

Solution of Given Problem​

Intuition and Approach​

The KMP algorithm follows these steps:

  1. Preprocessing the Pattern: Compute the longest proper prefix which is also a suffix (lps) array.
  2. Searching the Text: Use the lps array to skip characters in the text while matching the pattern.

Approaches​

Codes in Different Languages​

Written by sjain1909
#include <bits/stdc++.h>
using namespace std;
void computeLPSArray(string& pat, int M, vector<int>& lps) {
 int length = 0;  
 lps[0] = 0;     
 int i = 1;

 while (i < M) {
     if (pat[i] == pat[length]) {
         length++;
         lps[i] = length;
         i++;
     } else {
         if (length != 0) {
             length = lps[length - 1];
         } else {
             lps[i] = 0;
             i++;
         }
     }
 }
}

void KMPSearch(string& pat, string& txt) {
 int M = pat.length();
 int N = txt.length();

 vector<int> lps(M);

 computeLPSArray(pat, M, lps);

 int i = 0; 
 int j = 0; 
 while (i < N) {
     if (pat[j] == txt[i]) {
         j++;
         i++;
     }

     if (j == M) {
         cout << "Pattern found at index " << i - j << "\n";
         j = lps[j - 1];
     } else if (i < N && pat[j] != txt[i]) {
         if (j != 0) {
             j = lps[j - 1];
         } else {
             i++;
         }
     }
 }
}

int main() {
 string txt, pat;
 cout << "Enter the text: ";
 cin >> txt;
 cout << "Enter the pattern: ";
 cin >> pat;

 KMPSearch(pat, txt);

 return 0;
}

Complexity Analysis​

  • Time Complexity: O(N+M)O(N + M) where N is the length of the text and M is the length of the pattern.
  • Space Complexity: O(M)O(M) for the lps array.

Video Explanation of Given Problem​

Authors:

Loading...