Submission #1339318

#TimeUsernameProblemLanguageResultExecution timeMemory
1339318javkhlantogsPalindromes (APIO14_palindrome)C++20
100 / 100
49 ms69104 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	ll next[26],cnt,link,length;
};
vector<node> t(300001);
string s;
ll sz=2,last=0;
ll getlink(ll u,ll pos){
	while(pos-1-t[u].length<0 or s[pos-1-t[u].length]!=s[pos]){
		u=t[u].link;
	}
	return u;
}
void add(ll pos){
	ll u=getlink(last,pos);
	ll c=s[pos]-'a';
	if(t[u].next[c]==0){
		t[sz].length=t[u].length+2;
		if(t[sz].length==1) t[sz].link=0;
			else t[sz].link=t[getlink(t[u].link,pos)].next[c];
		t[u].next[c]=sz;
		sz++;
	}
	last=t[u].next[c];
	t[last].cnt++;
}
int main(){
	ll n,i,j,k,q;
	cin>>s;
	n=s.size();
	t[0].link=1;
	t[0].length=0;
	t[1].link=0;
	t[1].length=-1;
	for(i=0 ; i<n ; i++) add(i);
	ll ans=0;
	for(i=sz-1 ; i>=2 ; i--){
		t[t[i].link].cnt+=t[i].cnt;
		ans=max(ans,t[i].length*t[i].cnt);
	}
	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...