C++ KMP Approach


#1
vector<int> prefix(string str)
{
int n=str.length();
vector<int> lcs(n);
int i;
int temp = 0;
lcs.push_back(0);
for(i=1;i<n;i++)
{
    int j=lcs[i-1];
    while(j>0 && str[i]!=str[j])
    {
        j=lcs[j-1];
    }
    if(str[i]==str[j])
        j++;
    lcs[i]=j;
    
    
}
return lcs;
}

int KMP(string text,string pattern)
{
int m=text.length(),n=pattern.length();
vector<int> lcs = prefix(pattern);
int i=0,j=0;
while(i<m && j<n)
{
    if(text[i]==pattern[j])
    {
        i++;
        j++;
    }
    else
    {
        if(j!=0)
            j=lcs[j-1];
        else
            i++;
    }
}
if(j==n)
{
    return i-n;
}
return -1;



}
int Solution::strStr(const string A, const string B) {

int index = KMP(A,B);
return index;
}