SPOJ – LPS – Longest Palindromic Substring

S
Problem NameLPS – Longest Palindromic Substring
JudgeSPOJ
Problem Linkhttps://www.spoj.com/problems/LPS/en/
Algorithms & DSString Hashing, Binary Search
#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)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!