← Back to DSA Course | Chapter 3: Strings | Lesson 5 of 6

KMP Algorithm क्या है

KMP एक smart word-search helper जैसा है जो याद रखता है कि उसने पहले से क्या match किया, इसलिए इसे mismatch के बाद कभी text की शुरुआत से फिर शुरू नहीं होना पड़ता।

In this page:

  1. Pattern Matching
  2. LPS Array
  3. KMP Search
  4. Why KMP is Fast
  5. KMP Practice
Syntax
markup 
lps = [0] * len(pattern)          # build LPS array
# fill lps from the pattern

i = j = 0
while i < len(text):
    if text[i] == pattern[j]:
        i += 1
        j += 1
    elif j > 0:
        j = lps[j - 1]
    else:
        i += 1

Pattern Matching

Knuth-Morris-Pratt (KMP) algorithm एक text के अंदर एक pattern search करता है बिना text pointer को कभी पीछे move किए, mismatch के बाद भी, जो इसे repeated substructure वाले texts पर naive pattern matching से तेज़ बनाता है।

उदाहरण: Pattern Matching

#include <iostream>
using namespace std;
int main() {
    string text = "aabaabaaa", pattern = "aab";
    size_t pos = text.find(pattern);
    cout << "Pattern found at index " << pos << " (KMP finds this without rechecking text)" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        String text = "aabaabaaa", pattern = "aab";
        int pos = text.indexOf(pattern);
        System.out.println("Pattern found at index " + pos + " (KMP finds this without rechecking text)");
    }
}
text, pattern = "aabaabaaa", "aab"
pos = text.find(pattern)
print(f"Pattern found at index {pos} (KMP finds this without rechecking text)")
#include <stdio.h>
#include <string.h>
int main() {
    char text[] = "aabaabaaa", pattern[] = "aab";
    char *pos = strstr(text, pattern);
    printf("Pattern found at index %ld (KMP finds this without rechecking text)\n", pos - text);
    return 0;
}

LPS Array

LPS (longest proper prefix that is also a suffix) array per pattern एक बार precomputed होता है, और यह pattern के हर prefix के लिए store करता है कि उस prefix का कितना हिस्सा इसका खुद का suffix भी है, जो बिल्कुल वही है जो KMP को बताता है कि mismatch पर कितनी safely skip कर सकता है।

उदाहरण: LPS Array

#include <iostream>
using namespace std;
int main() {
    string pat = "aabaab";
    int m = pat.length();
    int lps[10] = {0};
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    for (int j = 0; j < m; j++) cout << lps[j] << " ";
    cout << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        String pat = "aabaab";
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0, i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        for (int x : lps) System.out.print(x + " ");
    }
}
pat = "aabaab"
m = len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
    if pat[i] == pat[length]:
        length += 1; lps[i] = length; i += 1
    elif length:
        length = lps[length - 1]
    else:
        lps[i] = 0; i += 1
print(lps)
#include <stdio.h>
#include <string.h>
int main() {
    char pat[] = "aabaab";
    int m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    for (int j = 0; j < m; j++) printf("%d ", lps[j]);
    printf("\n");
    return 0;
}

KMP Search

Search के दौरान, KMP text और pattern को character by character compare करता है, और mismatch होते ही, scratch से restart करने के बजाय, यह LPS array उपयोग करके pattern pointer को अगली sensible position तक आगे jump करता है।

उदाहरण: KMP Search

#include <iostream>
using namespace std;
int main() {
    string text = "abxabcabcaby", pat = "abcaby";
    int n = text.size(), m = pat.size();
    int lps[10] = {0};
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    i = 0; int j = 0;
    while (i < n) {
        if (text[i] == pat[j]) { i++; j++; }
        if (j == m) { cout << "Found at " << i - j << endl; break; }
        else if (i < n && text[i] != pat[j]) { if (j) j = lps[j - 1]; else i++; }
    }
    return 0;
}
public class Main {
    public static void main(String[] args) {
        String text = "abxabcabcaby", pat = "abcaby";
        int n = text.length(), m = pat.length();
        int[] lps = new int[m];
        int len = 0, i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        i = 0; int j = 0;
        while (i < n) {
            if (text.charAt(i) == pat.charAt(j)) { i++; j++; }
            if (j == m) { System.out.println("Found at " + (i - j)); break; }
            else if (i < n && text.charAt(i) != pat.charAt(j)) { if (j != 0) j = lps[j - 1]; else i++; }
        }
    }
}
text, pat = "abxabcabcaby", "abcaby"
n, m = len(text), len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
    if pat[i] == pat[length]:
        length += 1; lps[i] = length; i += 1
    elif length:
        length = lps[length - 1]
    else:
        lps[i] = 0; i += 1
i = j = 0
while i < n:
    if text[i] == pat[j]:
        i += 1; j += 1
    if j == m:
        print("Found at", i - j); break
    elif i < n and text[i] != pat[j]:
        j = lps[j - 1] if j else 0
        if j == 0: i += 1
#include <stdio.h>
#include <string.h>
int main() {
    char text[] = "abxabcabcaby", pat[] = "abcaby";
    int n = strlen(text), m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    i = 0; int j = 0;
    while (i < n) {
        if (text[i] == pat[j]) { i++; j++; }
        if (j == m) { printf("Found at %d\n", i - j); break; }
        else if (i < n && text[i] != pat[j]) { if (j) j = lps[j - 1]; else i++; }
    }
    return 0;
}

Why KMP is Fast

LPS-guided skipping के कारण, KMP कुल O(n + m) time में चलता है, जहां n text length है और m pattern length है, lots of repetition वाले texts पर naive approach के O(n × m) worst case की तुलना में एक बड़ा improvement।

उदाहरण: Why KMP is Fast

#include <iostream>
using namespace std;
int main() {
    int n = 1000, m = 5;
    cout << "Naive worst case: " << n * m << " comparisons" << endl;
    cout << "KMP worst case: " << n + m << " comparisons" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int n = 1000, m = 5;
        System.out.println("Naive worst case: " + (n * m) + " comparisons");
        System.out.println("KMP worst case: " + (n + m) + " comparisons");
    }
}
n, m = 1000, 5
print("Naive worst case:", n * m, "comparisons")
print("KMP worst case:", n + m, "comparisons")
#include <stdio.h>
int main() {
    int n = 1000, m = 5;
    printf("Naive worst case: %d comparisons\n", n * m);
    printf("KMP worst case: %d comparisons\n", n + m);
    return 0;
}

KMP Practice

KMP को असल में समझने का सबसे अच्छा तरीका इसे internal repetition वाले एक pattern पर हाथ से trace करना है, जैसे aabaabaaa, और देखना कि LPS array इसे पहले से matched characters फिर से check करने से कैसे रोकता है।

उदाहरण: KMP Practice

#include <iostream>
using namespace std;
int main() {
    string pat = "aabaabaaa";
    int m = pat.length();
    int lps[10] = {0};
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    cout << "LPS for \"" << pat << "\": ";
    for (int j = 0; j < m; j++) cout << lps[j] << " ";
    cout << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        String pat = "aabaabaaa";
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0, i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        System.out.print("LPS for \"" + pat + "\": ");
        for (int x : lps) System.out.print(x + " ");
    }
}
pat = "aabaabaaa"
m = len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
    if pat[i] == pat[length]:
        length += 1; lps[i] = length; i += 1
    elif length:
        length = lps[length - 1]
    else:
        lps[i] = 0; i += 1
print(f'LPS for "{pat}":', lps)
#include <stdio.h>
#include <string.h>
int main() {
    char pat[] = "aabaabaaa";
    int m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    printf("LPS for \"%s\": ", pat);
    for (int j = 0; j < m; j++) printf("%d ", lps[j]);
    printf("\n");
    return 0;
}
Related Topics

Rabin-Karp Algorithm क्या है · Kadane का Algorithm · Anagram और Frequency Count · String Reversal और Palindrome

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. len = lps[len - 1] के बजाय एक step पीछे move करके (len--) mismatch पर LPS array गलत compute करना।
  2. Mismatch के बाद text pointer को पीछे move करना, जो naive search को O(n * m) बनाता है और जिससे KMP बचता है।
  3. j = lps[j - 1] reset न करके एक पूरे match के बाद ज़्यादा matches ढूंढना जारी रखना भूल जाना।
🔒

Chapter Quiz — Complete all 6 topics to unlock

0/6 topics done

Complete these topics first:

← Previous Lesson Anagram and Frequency Count Next Lesson → Rabin-Karp Algorithm

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.