Submission #475270

#	Time	Username	Problem	Language	Result	Execution time	Memory
475270		KhaledFarhat	Palindromes (APIO14_palindrome)	C++14	100 / 100	70 ms	61176 KiB

palindrome

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

struct PalindromeNode {
	PalindromeNode(int length, int suffixLink)
		:	length(length), suffixLink(suffixLink), frequency(1) {
		memset(nextNode, -1, sizeof nextNode);		
	}
		
	int length;
	int suffixLink;
	int nextNode[26];
	
	int frequency;
};

struct PalindromicTree {
	PalindromicTree() 
		:	NULL_PALINDROME(0), EMPTY_PALINDROME(1),
			longestSuffixPalindrome(EMPTY_PALINDROME) {
		nodes.push_back(PalindromeNode(-1, NULL_PALINDROME));
		nodes.push_back(PalindromeNode(0, NULL_PALINDROME));
	}
	
	// return true of found a new palindrome
	bool appendLetter(char letter) {
		s += letter;
		
		int index = (int)s.size() - 1;
		int suffixLink = longestSuffixPalindrome;
		
		// searching for longest palindrome in the new suffix
		while (true) {
			int R = index;
			int L = R - nodes[suffixLink].length - 1;
						
			if (L >= 0 && s[L] == s[R]) {
				break;
			}
			else {
				suffixLink = nodes[suffixLink].suffixLink;
			}
		}
				
		// the palindrome already exists
		if (nodes[suffixLink].nextNode[letter - 'a'] != -1) {
			longestSuffixPalindrome = nodes[suffixLink].nextNode[letter - 'a'];
			++nodes[longestSuffixPalindrome].frequency;
			
			return false;
		}
		
		// found a new palindome
		int newNode = fetchNode(nodes[suffixLink].length + 2);
		
		nodes[suffixLink].nextNode[letter - 'a'] = newNode;
		longestSuffixPalindrome = newNode;
				
		// finding the suffix link of the new node
		if (nodes[newNode].length != 1) {
			while (true) {
				suffixLink = nodes[suffixLink].suffixLink;
								
				int R = index;
				int L = R - nodes[suffixLink].length - 1;
				
				if (L >= 0 && s[L] == s[R]) {
					nodes[newNode].suffixLink = nodes[suffixLink].nextNode[letter - 'a'];
					break;
				}
			}
		}
		
		return true;
	}
	
	// maintain the frequency of each palindome
	void propagate() {
		for (int i = (int)nodes.size() - 1; i >= 0; --i) {
			int parent = nodes[i].suffixLink;
			nodes[parent].frequency += nodes[i].frequency;
		}
	}

	// return the index of the new fetched node
	int fetchNode(int length) {
		return fetchNode(length, EMPTY_PALINDROME);
	}

	// return the index of the new fetched node
	int fetchNode(int length, int suffixLink) {
		nodes.push_back(PalindromeNode(length, suffixLink));
		
		return (int)nodes.size() - 1;
	}
	
	const int NULL_PALINDROME; // palindrome of length -1
	const int EMPTY_PALINDROME; // palindrome of length 0
	int longestSuffixPalindrome;
	vector<PalindromeNode> nodes;
	string s;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s;
	cin >> s;
	PalindromicTree tree;
	
	for (char letter : s) {
		tree.appendLetter(letter);
	}
	
	tree.propagate();
	
	long long maxOccurrenceValue = LLONG_MIN;
	
	for (PalindromeNode& palindrome : tree.nodes) {
		long long occurrenceValue = 1LL * palindrome.length * palindrome.frequency;
				
		maxOccurrenceValue = max(maxOccurrenceValue, occurrenceValue);
	}
	
	cout << maxOccurrenceValue;
	
	return 0;
}

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