C++ solution using LPS array


#1
vector<int> computeLPSArray(string s){
    int n = s.length();
    vector<int> LPS(n);
 
    int j = 0;
    LPS[0] = 0; 
 
    
    int i = 1;
    while (i < n){
        if (s[i] == s[j]){
            j++;
            LPS[i] = j;
            i++;
        }
        else{
            if (j != 0){
                j = LPS[j-1];
            }
            else{
                LPS[i] = 0;
                i++;
            }
        }
    }
    return LPS;
}

int Solution::solve(string s) {
    string rs = s;
    reverse(rs.begin(), rs.end());
    string c = rs + "$" + s;
    vector<int> LPS = computeLPSArray(c);
    return (s.length() - LPS.back());
}