PROBLEM LINK:
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Given a string s, calculate the sum of palindromeness of all the substrings of s, where palindromeness of any palindrome t is defined as 1 if |t| = 1 otherwise it is 1 + palindromeness of first half of t. Note that palindromeness is 0 if string is not a palindrome.
EXPLANATION:
In this problem, we essentially have to find all distinct palindromes, their counts and their palindromeness. First of all notice that the number of distinct palindromes in a string of length n is atmost n (to prove this pay attention to the number of distinct palindromes that can end at any position i). Now to calculate the count of all distinct palindromes we will build a palindromic tree (explained in much detail here and here ) of the given string s. In brief, palindromic tree is a tree whose vertices denote palindromes and there exists a directed edge from u to v if v = xux for some character x that is palindrome v can be formed by adding x in palindrome u. In addition to normal edges, we have suffixLinks which points from u to v if v is the longest suffix palindrome of u.
In addition to the information which is typically stored in a vertex of palindromic tree we will store a variable count which stores the number of indices where the palindrome associated with this vertex is the longest palindrome and also the reverse suffixLinks (its significance will become clear later). To calculate the count we keep track of longest palindrome while iterating over the string. That is whenever we add a new character, check whether the longest suffix palindrome is already present in the tree, if it is then increment its count otherwise create a new vertex and initialize its count by 1. And populating reverse suffixLink is also very easy, whenever we add a suffixLink, add a reverse suffixLink edge also. In this way we will build the palindromic tree.
1. Calculating count of all palindromes
Till now, at each vertex, we have the count of the number of indices where this is the longest palindrome. But this palindrome(lets call it t) can also end at those indices where some other palindrome is longest and palindrome t is its suffix. That is, this vertex is reachable by some vertex via a suffixLink path. Now to find all occurrences of t we will run a dfs (thats why we have also stored reverse suffixLinks) over the tree, treating only reverse suffixLink as edges and at each vertex we will add the count variable of all of its children. Since we have all the occurrences of palindromes of its children (since dfs had already ran on them) we now have all the indices where t is not the longest palindrome rather it is a suffix of longest palindrome. Add this to the count variable of t’s vertex.
2. Calculating Palindromeness
To calculate palindromeness, we again run a dfs(infact the two dfs can be merged together) on palindromic tree treating reverse suffixLinks as edges. While traversing the tree in dfs order, we will maintain an array P[] which stores the palindromeness of all prefix of string corresponding to vertex which we are currently proccessing. Below is a pseudocode which helps us understand how array P[] is updated
Pseudo Code
void dfs(int u)
{
int i, v;
if( T[u].len == 1 ) P[1] = 1;
else P[T[u].len] = P[T[u].len/2] + 1;
T[u].palindromness = P[T[u].len];
for(i = 0; i< T[u].revSuffixLink.size(); i++) {
v = T[u].revSuffixLink[i];
dfs(v);
T[u].count += T[v].count;
}
P[T[u].len] = 0;
}
The time complexity of both dfs and building the palindromic tree is \mathcal{O}(n) due to our observation on the upper bound on number of distinct palindromes.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.