Submission #173639

#	Time	Username	Problem	Language	Result	Execution time	Memory
173639		Pajaraja	회문 (APIO14_palindrome)	C++17	100 / 100	63 ms	36372 KiB

palindrome

#include <bits/stdc++.h>
#define MAXN 300007
using namespace std;
struct node {int nxt[26],l,suf; long long br;};
node tree[MAXN];
int br=2,suff=2;
long long res=0;
string s;
void add(int x)
{
	int cur=suff,curl=0;
	int ch=s[x]-'a';
	while(true)
	{
		curl=tree[cur].l;
		if(x-curl-1>=0 && s[x-curl-1]==s[x]) break;
		cur=tree[cur].suf;
	}
	if(tree[cur].nxt[ch]) 
	{
		suff = tree[cur].nxt[ch];
		tree[suff].br++;
		return;
	}
	br++;
	suff=br;
	tree[br].l=tree[cur].l+2;
	tree[cur].nxt[ch]=br;
	tree[br].br=1;
	for(int i=0;i<26;i++) tree[br].nxt[i]=0;
	if(tree[br].l==1) 
	{
		tree[br].suf=2;
		return;
	}
	while(true)
	{
		cur=tree[cur].suf;
		curl=tree[cur].l;
		if(x-curl-1>=0 && s[x-curl-1]==s[x]) break;
	}
	tree[br].suf=tree[cur].nxt[ch];
}
int main()
{
	int n;
	cin>>s; n=s.size();
	tree[1].l=-1; tree[1].suf=1; for(int i=0;i<26;i++) tree[1].nxt[i]=0;
	tree[2].l=0; tree[2].suf=1; for(int i=0;i<26;i++) tree[2].nxt[i]=0;
	for(int i=0;i<s.size();i++) add(i);
	for(int i=br;i>0;i--)
	{
		res=max(res,tree[i].br*tree[i].l);
		tree[tree[i].suf].br+=tree[i].br;
	}
	cout<<res;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++) add(i);
              ~^~~~~~~~~
palindrome.cpp:46:6: warning: variable 'n' set but not used [-Wunused-but-set-variable]
  int n;
      ^

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