Submission #21913

#	Time	Username	Problem	Language	Result	Execution time	Memory
21913		Yousef_Salama	Palindromes (APIO14_palindrome)	C++14	100 / 100	96 ms	67804 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

char s[MAXN];
int N;

int suflink[MAXN], g[MAXN][26], length[MAXN], flag[MAXN], M, p;
vector <int> G[MAXN];

void init(){
	memset(suflink, -1, sizeof suflink);
	memset(g, -1, sizeof g);

	length[0] = -1;
	length[1] = 0;

	suflink[1] = 0;
	G[0].push_back(1);

	M = 2;
	p = 1;
}

void extend(int i){
	while((i - length[p] - 1 < 0) || (s[i] != s[i - length[p] - 1]))
		p = suflink[p];

	if(g[p][s[i] - 'a'] != -1){
		flag[g[p][s[i] - 'a']]++;
		p = g[p][s[i] - 'a'];
	}else{
		int q = M++;
		g[p][s[i] - 'a'] = q;

		length[q] = length[p] + 2;

		while(true){
			if(p == 0){
				suflink[q] = 1;
				break;
			}

			p = suflink[p];
			if((i - length[p] - 1 >= 0) && (s[i] == s[i - length[p] - 1])){
				suflink[q] = g[p][s[i] - 'a'];
				break;
			}
		}

		G[suflink[q]].push_back(q);

		flag[q]++;
		p = q;
	}
}

int occ[MAXN];
long long solve(int i){
	occ[i] = flag[i];
	long long r = 0;

	for(int j : G[i]){
		r = max(r, solve(j));
		occ[i] += occ[j];
	}
    r = max(r, (long long)occ[i] * length[i]);
    
	return r;
}
int main(){
	scanf("%s", s);
	N = strlen(s);

	init();
	for(int i = 0; i < N; i++)
		extend(i);
		
	printf("%lld\n", solve(0));

	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:73:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
                ^

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