KMP algo.txt

vector<int> constructLps(string s){
    int n=s.length();
    vector<int> lps(n);
    lps[0]=0;
    int j=0,i=1;
    while(i<n){
        if(s[i]==s[j]){
            lps[i]=j+1;
            i++;
            j++;
        }
        else{
            if(j!=0)
            j=lps[j-1];
            else{
                lps[i]=0;
                i++;
            }
        }
    }
    return lps;
}
int Solution::strStr(const string A, const string B) {
    if(B.length()>A.length())
    return -1;
    vector<int> lps=constructLps(B);
    int i=0,j=0,n1=A.length(),n2=B.length();
    while(i<n1 and j<n2){
        if(A[i]==B[j]){
            i++;
            j++;
        }
        else{
            if(j!=0)
            j=lps[j-1];
            else
            i++;
        }
    }
    if(j==n2)
    return i-j;
    return -1;
    
}