Codeforces – Palindromic characteristics

C
Problem NamePalindromic characteristics
JudgeCodeforces
Problem Linkhttps://codeforces.com/contest/835/problem/D
Algorithms & DSString Hashing
#include<bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll MX=5000; constexpr ll base=29; constexpr ll mod=1000000007; 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); hsh[0]=s[0]-'a'+1; for(ll i=1;i<len;i++)hsh[i]=((hsh[i-1]*base)+(s[i]-'a'+1))%mod; revhsh.resize(len+5); revhsh[0]=s[len-1]-'a'+1; for(ll i=1,j=len-2;i<len;i++,j--)revhsh[i]=((revhsh[i-1]*base)+(s[j]-'a'+1))%mod; } int main() { ctPow(); string s; cin>>s; ctHsh(s); ll len=s.size(); unordered_map<ll,ll>mp; for(ll i=0;i<len;i++)mp[s[i]-'a'+1]=1; ll arr[len+6]; for(ll i=0;i<=len;i++)arr[i]=0; //arr[1]=len; for(ll sz=1;sz<=len;sz++){ for(ll idx=sz-1,revidx=len-1;idx<len;idx++,revidx--){ ll lidx=idx-sz; ll lrevidx=revidx-sz; ll fro=hsh[idx]; if(lidx>=0)fro=fro-(hsh[lidx]*basePow[sz])%mod; if(fro<0)fro+=mod; ll rev=revhsh[revidx]; if(lrevidx>=0)rev=rev-(revhsh[lrevidx]*basePow[sz])%mod; if(rev<0)rev+=mod; if(fro==rev){ if(mp[fro]==0){ ll nsz=sz/2; ll r=lidx+nsz; ll tmp=hsh[r]; if(lidx>=0)tmp-=(hsh[lidx]*basePow[nsz])%mod; if(tmp<0)tmp+=mod; mp[fro]=mp[tmp]+1; } arr[mp[fro]]++; } } } for(ll i=len-1;i>=1;i--)arr[i]+=arr[i+1]; for(ll i=1;i<=len;i++){ if(i>1)cout<<" "; cout<<arr[i]; } cout<<"\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 !!