UVa 11475 - Extend to Palindrome Solution

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string s;
string t;
vector<int> lps(int(1e5+1));
int ans;
void calc(){
    int m=s.size(),len=0;
    for(int i=1;i<m;){
        if(s[i]==s[len])
            lps[i++]=++len;
        else
            if(len)
                len=lps[len-1];
            else
                lps[i++]=0;
    }
}
void kmp(){
    calc();
    int m=s.size(),n=t.size(),i=0,j=0;
    while(i<n){
        if(s[j]==t[i])
            i++,j++;
        if(j==m){
            ans=m,j=lps[j-1];
            return;
        }
        if(i==n){
            ans=j;
            return;
        }
        else if(i<n&&s[j]!=t[i])
            if(j)
                j=lps[j-1];
            else
                i++;
    }
}
int main(){
    while(cin>>t){
        s=t;
        reverse(s.begin(),s.end());
        kmp();
        cout<<t<<s.substr(ans,s.size()-ans)<<endl;
    }
}