Submission #205606

#	Time	Username	Problem	Language	Result	Execution time	Memory
205606		mihai50000	Palindromes (APIO14_palindrome)	C++17	0 / 100	48 ms	30228 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

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

Compilation message (stderr)

palindrome.cpp:76: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