Submission #1326783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326783		goats_9	Palindromes (APIO14_palindrome)	C++20	100 / 100	52 ms	54372 KiB

palindrome

/* Author: goats_9 */

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

using ll = long long;

struct eertree {
	enum { K = 26, A = 'a' };
	struct Node {
		vector<int> nxt = vector<int> (K, -1);
		ll len = 0, cnt = 0;
		int suf = 0;
		Node() = default;
	};
	vector<Node> tree;
	eertree() : tree(2, Node()) { tree[0].len = -1; }
	eertree(string s) : eertree() {
		int p = 1, n = (int)s.size();
		for (int i = 0; i < n; i++) {
			while (i <= tree[p].len || s[i] != s[i - tree[p].len - 1]) p = tree[p].suf;
			if (tree[p].nxt[s[i] - A] == -1) {
				tree[p].nxt[s[i] - A] = (int)tree.size();
				tree.push_back(Node());
				tree.back().len = tree[p].len + 2;
			}
			int q = tree[p].nxt[s[i] - A];
			if (tree[q].len == 1) {
				tree[q].suf = 1;
				tree[q].cnt++;
				p = q;
				continue;
			}
			p = tree[p].suf;
			while (i <= tree[p].len || s[i] != s[i - tree[p].len - 1]) p = tree[p].suf;
			tree[q].suf = tree[p].nxt[s[i] - A];
			tree[q].cnt++;
			p = q;
		}
		for (int i = (int)tree.size() - 1; i >= 0; i--) tree[tree[i].suf].cnt += tree[i].cnt;
	}
};

int main() {
	string s;
	cin >> s;
	eertree tr(s);
	ll ans = 0;
	for (auto u : tr.tree) ans = max(ans, u.len * u.cnt);
	cout << ans;
	return 0;
}

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