Submission #1093967

#TimeUsernameProblemLanguageResultExecution timeMemory
1093967Trisanu_DasPalindromes (APIO14_palindrome)C++17
47 / 100
603 ms2104 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const mod=1e9+7;
int const base=727;
int const N=1e4+5;
string s;
int n;
int pre[N],suf[N];
int pw[N];
int hash_pre(int l,int r){
	l--;
	return ((pre[r]-((pre[l]*pw[r-l])%mod))+mod)%mod;
}
int hash_suf(int l,int r){
	r++;
	return ((suf[l]-((suf[r]*pw[r-l])%mod))+mod)%mod;
}
void make_hash(){
	pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=(pw[i-1]*base)%mod;
	int hsh=0;
	for (int i = 0; i < n; ++i)
	{
		hsh=(hsh*base)%mod;
		hsh=(hsh+s[i])%mod;
		pre[i+1]=hsh;
	}
	hsh=0;
	for(int i=n-1;i>=0;i--){
		hsh=(hsh*base)%mod;
		hsh=(hsh+s[i]);
		suf[i+1]=hsh;
	}
}
signed main(){
	cin>>s;
	n=s.length();
	make_hash();
	unordered_map<int,int> cnt;
	int h=0;
	for(int l=1;l<=n;l++)
		for(int r=l;r<=n;r++){
			h=hash_pre(l,r);
			if(h==hash_suf(l,r))
				cnt[h]+=(r-l)+1;
		}
	int maxx=0;
	for(auto p:cnt)
		maxx=max(maxx,p.second);
	cout<<maxx<<endl;
	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...