Submission #113104

#	Time	Username	Problem	Language	Result	Execution time	Memory
113104		Anai	Palindromes (APIO14_palindrome)	C++14	100 / 100	79 ms	46460 KiB

palindrome

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

using i64 = long long;

struct PalTree {
	struct Nod {
		map<char, int> tr;
		int suf, aps, l, r;

		inline int len() {
			return r - l + 1; }

 		Nod(int _l = -1, int _r = -1) {
			l = _l, r = _r;
			suf = -1;
			aps = 0; } };

	vector<Nod> pom;
	string str;
	int now;

	PalTree() {
		now = 0;
		pom.emplace_back();
		pom.emplace_back();
		pom[0].suf = pom[0].aps = 0, pom[0].r = -2, pom[0].l = 0; /* imaginary node */
		pom[1].suf = pom[1].aps = 0, pom[1].r = -1, pom[1].l = 0; /* null node */ }

	void push_back(char ch) {
		str.push_back(ch);

		while (now != 0) {
			if (pom[now].len() + 2 <= str.size() && str[str.size() - pom[now].len() - 2] == ch)
				break;
			now = pom[now].suf; }

		int &mynode = pom[now].tr[ch];
		if (mynode != 0) {
			now = mynode;
			pom[now].aps+= 1;
			return; }

		mynode = pom.size();
		pom.emplace_back();
		pom.back().l = str.size() - pom[now].len() - 2;
		pom.back().r = str.size() - 1;
		pom.back().aps = 1;

		int fall = pom[now].suf;
		now = mynode;

		if (pom[now].len() == 1) {
			pom[now].suf = 1;
			return; }

		while (fall != 0) {
			if (str[str.size() - pom[fall].len() - 2] == ch)
				break;
			fall = pom[fall].suf; }
		pom[now].suf = pom[fall].tr[ch]; }
	
	i64 get_ans() {
		i64 ans = 0;
		for (int i = pom.size() - 1; i > 1; --i) {
			pom[pom[i].suf].aps+= pom[i].aps;
			ans = max(ans, 1LL * pom[i].aps * pom[i].len()); }
		return ans; } };

int main() {
#ifdef HOME
	freopen("palindrome.in", "r", stdin);
	freopen("palindrome.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	string str;

	PalTree *pom = new PalTree();

	cin >> str;
	for (const auto &ch: str)
		pom->push_back(ch);
	cout << pom->get_ans() << endl;

	return 0; }

Compilation message (stderr)

palindrome.cpp: In member function 'void PalTree::push_back(char)':
palindrome.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pom[now].len() + 2 <= str.size() && str[str.size() - pom[now].len() - 2] == ch)
        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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