O(n) Solution - KMP Algorithm


#1

//KMP ALGORITHM

void fillLPS(const string &str,int lps[]){
int n=str.length(), len=0;
lps[0]=0;
int i=1;
while(i<n)
{
if(str[i]==str[len]){
len++;lps[i]=len;i++;
}
else{
if(len==0){lps[i]=0;i++;}
else{len=lps[len-1];}
}
}

}
int Solution::strStr(const string A, const string B) {
int n=A.length();
int m=B.length();
int lps[m];
fillLPS(B,lps);
int i=0,j=0;
while(i<n){
if(B[j]==A[i]){i++;j++;}
if(j==m){return(i-j);}
else if(i<n && B[j]!=A[i]){
if(j==0)i++;
else j=lps[j-1];
}
}
return -1;
}