SPOJ – EPALIN – Extend to Palindrome

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll>pi;
void ctPre(string s)
{
    ll len=s.size();
    pi.resize(len+5);
    pi[0]=0;
    for(ll i=1;i<len;i++){
        ll j=pi[i-1];
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
}

int main()
{
    string s;
    while(cin>>s){
        ll len=s.size();
        string pt=s;
        reverse(pt.begin(),pt.end());
        pt+="#";
        pt+=s;
        ll ptlen=pt.size();
        ctPre(pt);
        ll idx=len-pi[ptlen-1]-1;
        cout<<s;
        for(ll i=idx;i>=0;i--)cout<<s[i];
        cout<<"\n";
    }
}
Code language: PHP (php)