SPOJ – LPS – Longest Palindromic Substring

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

constexpr ll MX=100000;
constexpr ll base=29;
constexpr ll mod=1e9+7;

vector<ll>basePow;
void ctPow()
{
    basePow.resize(MX+5);
    basePow[0]=1;
    for(ll i=1;i<=MX;i++)basePow[i]=(basePow[i-1]*base)%mod;
}

vector<ll>hsh,revHsh;
void ctHsh(string s)
{
    ll len=s.size();
    hsh.resize(len+5);
    revHsh.resize(len+5);
    hsh[0]=s[0]-'a'+1;
    for(ll i=1;i<len;i++)hsh[i]=(hsh[i-1]*base+(s[i]-'a'+1))%mod;
    reverse(s.begin(),s.end());
    revHsh[0]=s[0]-'a'+1;
    for(ll i=1;i<len;i++)revHsh[i]=(revHsh[i-1]*base+(s[i]-'a'+1))%mod;
}

ll getHsh(ll l, ll r, bool mode)
{
    ll val;
    if(mode==true){
        val=hsh[r];
        if((l-1)>=0)val-=(hsh[l-1]*basePow[r-l+1])%mod;
        if(val<0)val+=mod;
    }else{
        val=revHsh[r];
        if((l-1)>=0)val-=(revHsh[l-1]*basePow[r-l+1])%mod;
        if(val<0)val+=mod;
    }
    return val;
}

ll bs(ll l,ll r,ll len, bool mode)
{
    if(l>r)return 0;
    ll mid=l+(r-l)/2;
    ll ck=0,ans=0;
    ll sz=(mid*2);
    if(mode==false) sz--;
    for(ll i=sz-1;i<len;i++){
        ll val=getHsh(i-sz+1,i,true);
        ll rev=getHsh(len-1-(i),len-1-(i-sz+1),false);
        if(val==rev){
            ck=1;
            break;
        }
    }
    if(ck==1){
        ans=max(sz,bs(mid+1,r,len,mode));
    }else{
        ans=bs(l,mid-1,len,mode);
    }
    return ans;
}

int main()
{
    ctPow();
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ctHsh(s);
    n=s.size();
    if(n==1)cout<<"1\n";
    else{
        ll even=n/2;
        ll odd=n/2+(n%2);
        ll ans=bs(1,even,n,true);
        ans=max(ans,bs(1,odd,n,false));
        cout<<ans<<"\n";
    }
    return 0;
}
Code language: PHP (php)