KMP Algorithm in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <string.h>

void computeLPS(char *pat, int m, int *lps) {
    int len = 0, i = 1;
    lps[0] = 0;
    while (i < m) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMP(char *txt, char *pat) {
    int n = strlen(txt);
    int m = strlen(pat);
    int lps[m];
    computeLPS(pat, m, lps);
    int i = 0, j = 0;
    while (i < n) {
        if (txt[i] == pat[j]) {
            i++; j++;
        }
        if (j == m) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < n && txt[i] != pat[j]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
}

int main() {
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";
    KMP(txt, pat);
    return 0;
}

C Output

Pattern found at index 10

C++ Program

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

void computeLPS(string pat, vector<int> &lps) {
    int len = 0, i = 1;
    lps[0] = 0;
    while (i < pat.size()) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
    }
}

void KMP(string txt, string pat) {
    int n = txt.size(), m = pat.size();
    vector<int> lps(m, 0);
    computeLPS(pat, lps);
    int i = 0, j = 0;
    while (i < n) {
        if (txt[i] == pat[j]) { i++; j++; }
        if (j == m) {
            cout << "Pattern found at index " << i - j << endl;
            j = lps[j - 1];
        } else if (i < n && txt[i] != pat[j]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
}

int main() {
    string txt = "ABABDABACDABABCABAB";
    string pat = "ABABCABAB";
    KMP(txt, pat);
    return 0;
}

C++ Output

Pattern found at index 10

JAVA Program

class KMP {
    void computeLPS(String pat, int m, int lps[]) {
        int len = 0, i = 1;
        lps[0] = 0;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) len = lps[len - 1];
                else lps[i++] = 0;
            }
        }
    }

    void search(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        int lps[] = new int[m];
        computeLPS(pat, m, lps);
        int i = 0, j = 0;
        while (i < n) {
            if (txt.charAt(i) == pat.charAt(j)) { i++; j++; }
            if (j == m) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < n && txt.charAt(i) != pat.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
    }

    public static void main(String args[]) {
        String txt = "ABABDABACDABABCABAB";
        String pat = "ABABCABAB";
        new KMP().search(txt, pat);
    }
}

JAVA Output

Pattern found at index 10

Python Program

def computeLPS(pat, m, lps):
    length = 0
    i = 1
    lps[0] = 0
    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

def KMP(txt, pat):
    n = len(txt)
    m = len(pat)
    lps = [0] * m
    computeLPS(pat, m, lps)
    i = j = 0
    while i < n:
        if txt[i] == pat[j]:
            i += 1
            j += 1
        if j == m:
            print("Pattern found at index", i - j)
            j = lps[j - 1]
        elif i < n and txt[i] != pat[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMP(txt, pat)

Python Output

Pattern found at index 10

In-Depth Explanation

Example

Let's consider we have the string "ABABDABACDABABCABAB" and we are looking for the substring "ABABCABAB". A standard brute-force search would look at each position of the string one at a time, which can be extremely slow. KMP, instead, preprocesses the pattern into an array named LPS (Longest Prefix Suffix), which informs us about how much we can shift the pattern without re-comparing characters unnecessarily. This prevents redundant comparisons and enhances efficiency.

Real-Life Analogy

Suppose you are trying to look up the word "knowledge" in a book and look for the word every time you mismatch after seeing "knowl". You don't begin from the beginning; rather, you already know that "kno" is shared, so you can skip a couple of characters and proceed. This is precisely what KMP accomplishes by bypassing unnecessary checks. It is similar to seeking accurately in a dictionary without re-beginning from the very first page after each mismatch.

Why It Matters

The KMP algorithm is very significant because it takes O(n + m) time, where n is the text length and m is the pattern length. This is much faster than naive approaches, which take O(n * m) in the worst case. For highly large texts like DNA sequencing, log analysis, or searching keywords in huge documents, efficiency becomes vital.

Learning Insights

KMP shows how important preprocessing is in algorithms. We are essentially "remembering" valuable information about the pattern when we construct the LPS array, and this avoids unnecessary computation. This concept of preprocessing and avoiding redundant computation is recurring in most advanced algorithms and makes programmers think optimistically.

Interview Use Case

KMP is one of the most frequently requested string matching algorithms in coding interviews. Google, Microsoft, and Amazon usually ask string manipulation and pattern matching problems. Having knowledge of KMP demonstrates that you know not only brute force but also efficient searching. Interviewers usually ask candidates to describe the construction of the LPS table as well, so it is vital to understand that thoroughly.

Real-World Application

KMP algorithm finds extensive usage in text editors (such as finding a word in a document), compilers (finding particular tokens), search engines (keyword search), and even DNA pattern matching in bioinformatics. Any application where there is pattern searching in large datasets can utilize this effective algorithm.

SEO Optimized Closing Paragraph

The KMP Algorithm in C, C++, Java, and Python is among the most effective algorithms for matching a string pattern. Through the application of the Longest Prefix Suffix (LPS) array, KMP prevents superfluous comparisons and achieves a time complexity of O(n + m), which is significantly faster than brute force. String algorithms beginners must work on KMP because it is a common interview question and has real-world applications in text processing, search engines, and bioinformatics. Learning and implementing code for KMP algorithm in several programming languages such as C, C++, Java, and Python makes problem-solving stronger, technical interview confidence stronger, and efficiency in solving real-world programming problems better.