Submission #49591

#	Time	Username	Problem	Language	Result	Execution time	Memory
49591		jcg	Palindromes (APIO14_palindrome)	C++14	100 / 100	96 ms	66400 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

template<typename charT, typename Container>
struct palindromic_tree
{
	struct node
	{
		int slink;
		int length;
		Container next;
		node(int slink, int length) : slink(slink), length(length), next{{}} {}
		int operator[](int c) const { return next[c]; }
		int& operator[](int c) { return next[c]; }
	};

	palindromic_tree()
	{
		sink = 0;
		nodes.emplace_back(0, -1);
		nodes.emplace_back(0, 0);
	}

	int extend(const charT &c)
	{
		str.push_back(c);
		sink = get_link(sink);
		if (!nodes[sink][c])
		{
			nodes[sink][c] = nodes.size();
			int length = nodes[sink].length + 2;
			int slink = length == 1 ? 1 : nodes[get_link(nodes[sink].slink)][c];
			nodes.emplace_back(slink, length);
		}
		return sink = nodes[sink][c];
	}

	const node& operator[](int node_id) const { return nodes[node_id]; }
	int size() const { return nodes.size(); }

private:
	int sink;
	vector<node> nodes;
	vector<charT> str;

	int get_link(int v)
	{
		int n = str.size();
		while (n - nodes[v].length - 2 < 0 || str[n - 1] != str[n - nodes[v].length - 2])
			v = nodes[v].slink;
		return v;
	}
};

int main()
{
#ifdef jcg
	assert(freopen("input.in", "r", stdin));
	// assert(freopen("output.out", "w", stdout));
#else
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;

	palindromic_tree<int, array<int, 26>> tree;

	vector<int> endpos;
	for (char c : s)
		endpos.emplace_back(tree.extend(c-'a'));

	vector<int> occ(tree.size());
	for (int x : endpos) ++occ[x];

	long long ans = 0;
	for (int i = (int) tree.size()-1; i >= 2; --i)
	{
		ans = max(ans, (long long) tree[i].length * occ[i]);
		occ[tree[i].slink] += occ[i];
	}

	cout << ans << endl;

	return 0;
}

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