Submission #208557

#	Time	Username	Problem	Language	Result	Execution time	Memory
208557		steinum	Palindromes (APIO14_palindrome)	C++14	100 / 100	30 ms	35832 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
char s[N]; // 1-indexed
int T, idx, Tree[N][26], link[N], len[N], occ[N] , num[N], n;
inline void extend(int p) {
	while (s[p - len[T] - 1] != s[p]) T = link[T];
	int x = link[T], c = s[p] - 'a';
	while (s[p - len[x] - 1] != s[p]) x = link[x];
	if (!Tree[T][c]) {
		Tree[T][c] = ++idx;
		len[idx] = len[T] + 2;
		link[idx] = len[idx] == 1 ? 2 : Tree[x][c];
		num[idx] = 1 + num[link[idx]];
	} T = Tree[T][c],++occ[T];
}
long long build() {
	long long tot_pal=0;

	memset(Tree, 0, sizeof Tree);
	memset(occ, 0, sizeof occ);
	len[1] = -1, len[2] = 0;
	link[1] = link[2] = 1;
	T = idx = 2;
	for (int i = 1; i <= n; i++) {
		extend(i);
		tot_pal+=num[T];
		// cout<<"# "<<num[T]<<endl;
	}
	for (int i = idx; i > 2; i--) {
		occ[link[i]] += occ[i];
	}
	// for(int i=3;i<=idx;i++)cout<<len[i]<<' '<<occ[i]<<endl;
	return tot_pal;
}

int main(int argc, char const *argv[])
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	build();
	long long ma=0;
	for(int i=3;i<=idx;i++)ma=max(ma,(long long)len[i]*(long long)occ[i]);
	printf("%lld\n", ma);
	return 0;
}

Compilation message (stderr)

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

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