Submission #997423

#	Time	Username	Problem	Language	Result	Execution time	Memory
997423		UmairAhmadMirza	Palindromes (APIO14_palindrome)	C++17	0 / 100	38 ms	44268 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
int const N=3e5+5;
struct Node
{
	int len;
	int start,end;
	int child[26]={0};
	int suffix;
};

Node root1,root2;
Node tree[N];
long long cnt[N];

int curnode,ptr;
string s;

void insert_char(int k){
	// cout<<k<<endl;
	int tmp=curnode;
	while(!(k-tree[tmp].len>=1 && s[k]==s[k-(tree[tmp].len+1)]))
		tmp=tree[tmp].suffix;
	if(tree[tmp].child[s[k]-'a']!=0){
		curnode=tree[tmp].child[s[k]-'a'];
		return;
	}
	ptr++;
	tree[tmp].child[s[k]-'a']=ptr;
	tree[ptr].len=tree[tmp].len+2;
	tree[ptr].end=k;
	tree[ptr].start=k-(tree[ptr].len)+1;

	tmp=tree[tmp].suffix;
	curnode=ptr;
	if(tree[curnode].len==1){//root2 will be suffix
		tree[curnode].suffix=2;
		return;
	}
	while(!(k-tree[tmp].len>=1 && s[k]==s[k-(tree[tmp].len+1)]))
		tmp=tree[tmp].suffix;
	tree[curnode].suffix=tree[tmp].child[s[k]-'a'];

	return;
}

int main(){
	root1.len=-1;
	root1.suffix=1;
	root2.len=0;
	root2.suffix=1;
	tree[1]=root1;
	tree[2]=root2;
	ptr=2;
	curnode=1;
	cin>>s;
	int n=s.length();
	for (int i = 0; i < n; ++i)
		insert_char(i);
	// cout<<ptr<<endl;
	vector<pair<int,int>> v;
	for (int i = 3; i <=ptr; ++i)
	{
		cnt[i]=1;
		v.push_back({-tree[i].len,i});
	}
	sort(v.begin(), v.end());
	for(auto p:v)
		cnt[tree[p.second].suffix]+=cnt[p.second];
	long long mx=0;
	for(int i=3;i<=ptr;i++)
		mx=max(mx,cnt[i]*(tree[i].len));
	cout<<mx<<endl;
	return 0;
}

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