Knuth-Morris-Pratt (KMP) Algorithm

Description

The Knuth-Morris-Pratt (KMP) algorithm is used for pattern matching in a string. It preprocesses the pattern to create a partial match table (also known as the longest prefix suffix or LPS array), which allows the pattern to skip characters while searching in the text, thus improving efficiency.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

vector<int> computeLPS(string pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);

    int len = 0;

    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

void KMPSearch(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();

    vector<int> lps = computeLPS(pattern);
    int i = 0;
    int j = 0;

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            cout << "Pattern found at index " << i - j << endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
KMP Algorithm	O(n + m)	O(m)

Where:

• n: Length of the text to be searched.
• m: Length of the pattern.

← Back to Homepage