Submission #474027

#	Time	Username	Problem	Language	Result	Execution time	Memory
474027		jangwonyoung	Palindromes (APIO14_palindrome)	C++14	100 / 100	210 ms	98904 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e5+5;
int n;
string s;
int f[226];

int sz=1;
const int ts=6e5+5;
int ch[ts][26];
int fa[ts],len[ts];
int mp[ts];
int king[N];
vector<int>adj[ts];
int rsz[ts];

int fi[ts],pl[ts];
void dfs(int id){
	for(auto c:adj[id]){
		dfs(c);
		rsz[id]+=rsz[c];
	}
}
void dfs2(int id){
	for(auto c:adj[id]){
		dfs2(c);
		if(fi[c]!=0){
			int i=fi[c];
			int cl=len[id];
			int x=id;
			if(i+cl-1>=mp[x]){
				if(mp[x]-i+1>len[fa[x]]){
					pl[x]=mp[x]-i+1;
				}
			}
			fi[id]=max(fi[id],fi[c]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	for(int i='a'; i<='z' ;i++) f[i]=i-'a';
	cin >> s;n=s.size();s='?'+s;
	int x=1;
	for(int i=1; i<=n ;i++){
		char c=s[i];
		int y=++sz;len[y]=i;
		while(x && !ch[x][f[c]]){
			ch[x][f[c]]=y;
			x=fa[x];
		}
		if(!x){
			fa[y]=1;
		}
		else if(len[x]+1==len[ch[x][f[c]]]){
			fa[y]=ch[x][f[c]];
		}
		else{
			int w=ch[x][f[c]];
			int z=++sz;len[z]=len[x]+1;
			for(int j=0; j<26 ;j++) ch[z][j]=ch[w][j];
			fa[z]=fa[w];fa[w]=z;
			while(ch[x][f[c]]==w){
				ch[x][f[c]]=z;
				x=fa[x];
			}
			fa[y]=z;
		}
		king[i]=x=y;
	}
	for(int i=2; i<=ts ;i++){
		adj[fa[i]].push_back(i);
	}
	for(int i=n; i>=1 ;i--){
		int x=king[i];
		while(!mp[x]){
			mp[x]=i;x=fa[x];
		}
		rsz[king[i]]++;
	}
	dfs(1);
	x=1;
	int cl=0;
	for(int i=n; i>=1 ;i--){
		char c=s[i];
		while(ch[x][f[c]]==0){
			x=fa[x];
			cl=len[x];
		}
		x=ch[x][f[c]];
		cl++;
		if(fi[x]==0) fi[x]=i;
		if(i+cl-1>=mp[x]){
			if(mp[x]-i+1>len[fa[x]]){
				pl[x]=mp[x]-i+1;
			}
		}
	}
	dfs2(1);
	ll ans=0;
	for(int i=1; i<=sz ;i++){
		//cout << pl[i] << '\n';
		if(pl[i]!=0) ans=max(ans,1LL*pl[i]*rsz[i]);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:51:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |   while(x && !ch[x][f[c]]){
      |                       ^
palindrome.cpp:52:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |    ch[x][f[c]]=y;
      |            ^
palindrome.cpp:58:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |   else if(len[x]+1==len[ch[x][f[c]]]){
      |                                 ^
palindrome.cpp:59:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |    fa[y]=ch[x][f[c]];
      |                  ^
palindrome.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |    int w=ch[x][f[c]];
      |                  ^
palindrome.cpp:66:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |    while(ch[x][f[c]]==w){
      |                  ^
palindrome.cpp:67:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |     ch[x][f[c]]=z;
      |             ^
palindrome.cpp:89:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |   while(ch[x][f[c]]==0){
      |                 ^
palindrome.cpp:93:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |   x=ch[x][f[c]];
      |             ^

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