APIO 2014 Palindrome

Solution

First, construct the palindromic tree from the string. There are $O(N)$ distinct palindromes, so our tree will have $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: $O(N)$.

Memory: $O(N)$.

Code

#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];