Submission #205590

#	Time	Username	Problem	Language	Result	Execution time	Memory
205590		mihai50000	Palindromes (APIO14_palindrome)	C++17	0 / 100	51 ms	30232 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct PalTree
{
	struct Node
	{
		map <char, int> next;
		int link;
		int len;
		int cnt;
	};
	
	vector <Node> T;
	int n = 2;
	int ans = 0;
	
	PalTree(string str) : T(str.size() + 2)
	{
		T[1].link = T[1].len = 0;
		T[0].link = T[0].len = -1;
		
		int last = 0;
		int m = str.size();
		
		for(int i = 0; i < m; ++i)
		{
			char ch = str[i];
			int nod = last;
			
			while(ch != str[i - 1 - T[nod].len])
				nod = T[nod].link;
			
			if(T[nod].next.count(ch))
			{
				nod = T[nod].next[ch];
				T[nod].cnt++;
				last = nod;
				continue;
			}
			
			int act = n++;
			T[act].len = T[nod].len + 2;
			T[nod].next[ch] = act;
			
			int link = T[nod].link;
			
			while(link != -1)
			{
				if(ch == str[i - T[link].len - 1] && T[link].next.count(ch))
				{
						link = T[link].next[ch];
						break;
				}
				
				link = T[link].link;
			}
			
			if(link <= 0)
				link = 1;
			
			T[act].link = 1;
			T[act].cnt = 1;
			
			last = act;
		}
		
		for(int i = n - 1; i > 0; --i)
		{
			T[T[i].link].cnt += T[i].cnt;
			ans = max(ans, T[i].cnt * T[i].len);
		}
	}
};

main()
{
	string s;
	cin >> s;
	
	PalTree arb(s);
	
	cout << arb.ans << '\n';
}

Compilation message (stderr)

palindrome.cpp:79:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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