제출 #1338960

#제출 시각아이디문제언어결과실행 시간메모리
1338960javkhlantogs회문 (APIO14_palindrome)C++20
100 / 100
47 ms69128 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
// PALINDROMIC TREE!
struct node{
	ll next[26];
	ll length;
	ll link;
	ll cnt;
};
vector<node> t(300001);
ll sz=2,last=0;
string s;
ll getlink(ll v,ll pos){
	while(pos-1-t[v].length<0 or s[pos-1-t[v].length]!=s[pos]){
		v=t[v].link;
	}
	return v;
}
void update(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].length=0;
	t[0].link=1;
	t[1].length=-1;
	t[1].link=1;
	for(i=0 ; i<n ; i++) update(i);
	ll ans=0;
	for(i=sz-1 ; i>=2 ; i--){
		t[t[i].link].cnt+=t[i].cnt;
		ans=max(ans,t[i].cnt*t[i].length);
	}
	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...