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.

Complexity

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

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

Code

1#include <bits/stdc++.h>
2#define FOR(i, x, y) for (int i = x; i < y; i++)
3typedef long long ll;
4using namespace std;
5
6struct Node {
7    int nxt[26], sufflink;
8    ll len, cnt;
9    vector<int> edges;
10} tree[303030];