APIO 2014 - Palindrome

Solution

First, construct the palindromic tree from the string. There are $\mathcal{O}(N)$ distinct palindromes, so our tree will have $\mathcal{O}(N)$ nodes.

In addition to the standard information about a node's palindrome that we store in it (e.g. length and suffix link), store the number of times each node's palindrome was the maximum suffix. Let this number be $C_i$ for the $i$-th node.

Since each node's palindrome is a substring of the palindromes of the nodes in its subtree, the sum of $C_i$ in node $i$'s subtree gives us the number of occurrences of node $i$'s palindrome in the string.

We can then do a DFS to find the number of occurrences of each distinct palindrome in the string and then we simply check which one has the greatest occurrence value.

Implementation

Time Complexity: $\mathcal{O}(N)$

Memory Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
	int nxt[26], sufflink;
	ll len, cnt;
	vector<int> edges;
} tree[303030];