C++ Solution using LPS array in KMP Algorithm


#1
typedef long long int ll;
int Solution::solve(string A) {
    ll n=A.length();
    string B=A;
    reverse(B.begin(),B.end());
    string C=B+'*'+A;
    ll len=0;
    ll i=1;
    // cout << C << endl;
    vector<ll> lps(2*n);
    lps[0]=0;
    while(i<2*n){
        if(C[i]==C[len]){
            len++;
            lps[i]=len;
            i++;
        }
        else{
            if(len!=0){
                len=lps[len-1];
            }
            else{
                lps[i]=0;
                i++;
            }
        }
    }
    if(lps[(2*n)-1]==n+1){
        return 0;
    }
    // cout << lps[(2*n)-1] << endl;
    return n-lps[2*n-1]-1;
}


#2

why we need to add special character in the concate string.???