제출 #1338642

#제출 시각아이디문제언어결과실행 시간메모리
1338642javkhlantogs회문 (APIO14_palindrome)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p1=11,p2=131;
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(void){
	ios::sync_with_stdio(0); cin.tie(0);
	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<vector<ll>> mp(n+1,vector<ll>(p2,0));
	ll inv=powr(p1,p2-2);	
	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*powr(inv,n-i-j))%p2;
			}
			if(n-i<n){
				hash2=(hash2-h2[n-i]+p2)%p2;
				hash2=(hash2*powr(inv,i))%p2;
			}
			if(hash1==hash2) mp[j][hash1]++;
		}
	}
	ll ans=0;
	for(i=1 ; i<=n ; i++){
		for(j=0 ; j<p2 ; j++){
			ans=max(ans,i*mp[i][j]);
		}
	}
	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...