oj.uz

Submission #475270

# Submission time Handle Problem Language Result Execution time Memory
475270 2021-09-21T17:15:14 Z KhaledFarhat Palindromes (APIO14_palindrome) C++14
100 / 100
 70 ms 61176 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 280 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 0 ms 332 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 1 ms 312 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 0 ms 312 KB Output is correct
32 Correct 0 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2220 KB Output is correct
2 Correct 2 ms 2220 KB Output is correct
3 Correct 2 ms 2348 KB Output is correct
4 Correct 2 ms 2348 KB Output is correct
5 Correct 2 ms 2348 KB Output is correct
6 Correct 2 ms 2348 KB Output is correct
7 Correct 2 ms 2220 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15456 KB Output is correct
2 Correct 21 ms 15628 KB Output is correct
3 Correct 20 ms 15640 KB Output is correct
4 Correct 17 ms 15632 KB Output is correct
5 Correct 16 ms 15668 KB Output is correct
6 Correct 14 ms 15600 KB Output is correct
7 Correct 18 ms 15648 KB Output is correct
8 Correct 3 ms 844 KB Output is correct
9 Correct 6 ms 4584 KB Output is correct
10 Correct 17 ms 15648 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 60784 KB Output is correct
2 Correct 56 ms 61072 KB Output is correct
3 Correct 56 ms 61176 KB Output is correct
4 Correct 61 ms 61116 KB Output is correct
5 Correct 70 ms 61064 KB Output is correct
6 Correct 56 ms 61124 KB Output is correct
7 Correct 42 ms 31060 KB Output is correct
8 Correct 9 ms 1688 KB Output is correct
9 Correct 9 ms 1736 KB Output is correct
10 Correct 37 ms 31060 KB Output is correct
11 Correct 54 ms 61176 KB Output is correct
12 Correct 13 ms 4984 KB Output is correct