KMP Algorithm

17 Dec 2019

KMP Algorithm for Pattern Searching

Problem

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[].

OR

Implement strStr - locate a substring (needle) in a string (haystack). Return the first occurence of needle in haystack, or -1 if needle is not part of the haystack.

Solution

void LPS(const string B, vector<int> &lps){
    lps[0]=0;
    int i=1, len=0;
    while(i<B.size()){
        if(B[i]==B[len]){
            len++;
            lps[i]=len;
            i++;
        }
        else{
            if(len!=0){
                len = lps[len-1];
            }
            else{
                lps[i]=0;
                i++;
            }
        }
    }
}
int Solution::strStr(const string A, const string B) {
    if(A.size()==0 || B.size()==0 || B.size() > A.size()) return -1;
    vector<int> lps(B.size());
    LPS(B, lps);
    
    int i=0, j=0;
    while(i<A.size()){
        if(A[i]==B[j]){
            i++;
            j++;
        }
        if(j==B.size()){
            return i-j;
        }
        else if(i<A.size() && A[i]!=B[j]){
            if(j!=0) j=lps[j-1];
            else i++;
        }
    }
    return -1;
}

Reference - geeksforgeeks

P.S.

Take note