Submission #397598

#	Time	Username	Problem	Language	Result	Execution time	Memory
397598		Drew_	Palindromes (APIO14_palindrome)	C++14	100 / 100	60 ms	54880 KiB

palindrome

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define ll long long
#define pb push_back

const int MAX = 3e5 + 7;

struct Node
{
	int l, r;
	int len, occ = 0;

	int ch[26]; //adding a character
	int slink; //suffix link
};

int sz, cur;
Node tree[MAX]; //eertree

string s;
void addChar(int idx)
{
	int tmp = cur;
	while (1)
	{
		if (idx - tree[tmp].len >= 1 && s[idx] == s[idx - tree[tmp].len - 1])
			break;
		tmp = tree[tmp].slink;
	}

	if (tree[tmp].ch[s[idx] - 'a'] != 0)
	{
		cur = tree[tmp].ch[s[idx] - 'a'];
		return;
	}

	sz++;
	tree[tmp].ch[s[idx] - 'a'] = sz;
	tree[sz].len = tree[tmp].len + 2;
	tree[sz].r = idx;
	tree[sz].l = idx - tree[sz].len + 1;

	//getting suffix link
	tmp = tree[tmp].slink;
	cur = sz;
	if (tree[cur].len == 1)
	{
		tree[cur].slink = 2;
		return;
	}

	while (1)
	{
		if (idx - tree[tmp].len >= 1 && s[idx] == s[idx - tree[tmp].len - 1])
			break;
		tmp = tree[tmp].slink;
	}

	tree[cur].slink = tree[tmp].ch[s[idx] - 'a'];
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tree[1].len = -1;
	tree[1].slink = 1;
	tree[2].len = 0;
	tree[2].slink = 1;
	sz = 2; cur = 1;

	cin >> s;
	for (int i = 0; i < s.size(); ++i)
	{
		addChar(i);
		tree[cur].occ++;
	}

	ll res = 0;

	int indegree[MAX];
	vector<int> adj[MAX];
	queue<int> q;
	for (int i = 3; i <= sz; ++i)
	{
		adj[i].pb(tree[i].slink);
		indegree[tree[i].slink]++;
	}

	for (int i = 3; i <= sz; ++i)
		if (indegree[i] == 0)
			q.push(i);

	while (!q.empty())
	{
		int node = q.front();
		q.pop();

		res = max(res, 1LL * tree[node].len * tree[node].occ);

		for (int to : adj[node])
		{
			tree[to].occ += tree[node].occ;
			
			indegree[to]--;
			if (indegree[to] == 0)
				q.push(to);
		}
	}
	cout << res << '\n';

	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < s.size(); ++i)
      |                  ~~^~~~~~~~~~

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