Submission #376625

#	Time	Username	Problem	Language	Result	Execution time	Memory
376625		rainboy	Palindromes (APIO14_palindrome)	C11	100 / 100	54 ms	65152 KiB

palindrome

#include <stdio.h>
#include <string.h>

#define N	300000
#define A	26

long long max(long long a, long long b) { return a > b ? a : b; }

int tt[2 + N][A], ff[2 + N], fff[2 + N][A], len[2 + N], cnt[2 + N], _;

int node(int l) {
	len[_] = l;
	return _++;
}

void init() {
	int a;

	node(0), node(-1);
	ff[0] = 1;
	for (a = 0; a < A; a++)
		fff[0][a] = fff[1][a] = 1;
}

int main() {
	static char cc[N + 1];
	int n, i, t;
	long long ans;

	init();
	scanf("%s", cc), n = strlen(cc);
	for (i = 0, t = 0; i < n; i++) {
		int a = cc[i] - 'a';

		if (i == len[t] || cc[i - 1 - len[t]] != cc[i])
			t = fff[t][a];
		if (!tt[t][a]) {
			int t_ = node(len[t] + 2), f = tt[fff[t][a]][a];

			tt[t][a] = t_, ff[t_] = f;
			memcpy(fff[t_], fff[f], A * sizeof *fff[f]), fff[t_][cc[i - len[f]] - 'a'] = f;
		}
		t = tt[t][a];
		cnt[t]++;
	}
	for (t = _ - 1; t > 1; t--)
		cnt[ff[t]] += cnt[t];
	ans = 0;
	for (t = 2; t < _; t++)
		ans = max(ans, (long long) cnt[t] * len[t]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

palindrome.c: In function 'main':
palindrome.c:31:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

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