Submission #972085

#	Time	Username	Problem	Language	Result	Execution time	Memory
972085		UmairAhmadMirza	Palindromes (APIO14_palindrome)	C++17	47 / 100	862 ms	1784 KiB

palindrome

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27