Submission #1340434

#TimeUsernameProblemLanguageResultExecution timeMemory
1340434khangai11Palindromes (APIO14_palindrome)C++20
0 / 100
1 ms492 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
ll m1=1e9+7;
ll pwr(ll a,ll b){
	if(b==0){
		return 1;
	}
	ll ans=pwr(a,b/2);
	ans*=ans;
	ans%=m1;
	if(b%2==1){
		ans*=a;
		ans%=m1;
	}
	return ans;
}
void solve(){
	string s;
	cin>>s;
	vector<vector<ll>> sf(s.size(),vector<ll>(s.size()));
	for(ll a=0;a<s.size();a++){
		ll d=0;
		for(ll b=a;b<s.size();b++){
			d*=29;
			d+=(ll)(s[b]-'a'+1);
			d%=m1;
			sf[a][b]=d;
		}
	}
	for(ll a=s.size()-1;a>=0;a--){
		ll d=0;
		for(ll b=a;b>=0;b--){
			d*=29;
			d+=(ll)(s[b]-'a'+1);
			d%=m1;
			sf[a][b]=d;
		}
	}
	ll D=0;
	vector<ll> mp(1e9+7);
	for(ll a=0;a<s.size();a++){
		for(ll b=a;b<s.size();b++){
			if(sf[a][b]==sf[b][a]){
				mp[sf[a][b]]+=(b-a+1);
				D=max(D,mp[sf[a][b]]);
			}
		}
	}
	cout<<D<<endl;
}
signed main(){
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	ll t=1;
//	cin>>t;
	for(ll a=0;a<t;a++){
		solve();
	}
}
#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...