Submission #1338649

#TimeUsernameProblemLanguageResultExecution timeMemory
1338649javkhlantogsPalindromes (APIO14_palindrome)C++20
47 / 100
1096 ms17056 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p1=31,p2=1e9+7;
ll powr(ll a,ll b){
	if(b==0) return 1;
	ll v=powr(a,b/2);
	v=(v*v)%p2;
	if(b%2) v=(v*a)%p2;
	return v;
}
int main(){
	ll n,i,j,k,q;
	string s1,s2;
	cin>>s1;
	n=s1.size();
	s2=s1;
	reverse(s2.begin(),s2.end());
	vector<ll> h1(n),h2(n);
	h1[n-1]=s1[n-1]-'a';
	h2[n-1]=s2[n-1]-'a';
	for(i=n-2 ; i>=0 ; i--){
		h1[i]=(((s1[i]-'a')*powr(p1,n-1-i))%p2+h1[i+1])%p2;
		h2[i]=(((s2[i]-'a')*powr(p1,n-1-i))%p2+h2[i+1])%p2;
	}
	vector<unordered_map<ll,ll>> mp(n+1);
	ll inv=powr(p1,p2-2);
	vector<ll> inpow(n);
	for(i=0 ; i<n ; i++) inpow[i]=powr(inv,i);	
	for(i=0 ; i<n ; i++){
		for(j=1 ; j<=n-i ; j++){
			ll hash1=h1[i];
			ll hash2=h2[n-i-j];
			if(i+j<n){
				hash1=(hash1-h1[i+j]+p2)%p2;
				hash1=(hash1*inpow[n-i-j])%p2;
			}
			if(n-i<n){
				hash2=(hash2-h2[n-i]+p2)%p2;
				hash2=(hash2*inpow[i])%p2;
			}
			if(hash1==hash2) mp[j][hash1]++;
		}
	}
	ll ans=0;
	for(i=1 ; i<=n ; i++){
		for(auto v:mp[i]) ans=max(ans,v.second*i);
	}
	cout<<ans<<"\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...