Problem Link
Author: Aditya Shah
Tester: Sai Sandeep
Difficulty
Medium - HardPrerequisites
Palindromic TreeExplanation
Please read the basic palindromic tree from this website.
We will use the notations used in the tutorial above and build our solution upon it.
Consider the linear string / skew tree below:
Here, when we move to node having character ‘b’ (node 5), the palindromic tree automaton will first try to expand the palindrome path [1, 4]. When it fails, it will go to the suffix link of palindrome [1,4] which is [2, 4], again fails and goes to [3, 4], then to [4, 4] and finally gives up.
What happens when there are many siblings of node 5 with the same character ‘b’?. Say there are x children of node 4, each having some character != ‘a’. For each of them, our automaton will make 4 iterations!!
Say that instead of 4 nodes, we have a chain of N / 2 nodes each having a same character ‘a’ and x = N / 2. Then in this scenario, number of iterations/complexity would be (N / 2) * (N / 2) = O(N^2).
Lets observe what we are over doing here. When we fail to expand the largest suffix palindrome with the newly encountered character, we make transitions over to it’s suffix links. Now, for a single linear string, these transitions can be at most O(N) (see last para in explanation of blog above), but as we saw here, in case of tree, it can be O(N^2). We can do some pruning here. See that for each palindrome, either it can be expanded directly on seeing a new character or we search for the largest suffix link, that can expand it.
Hence we can make an extra transition table which gives a mapping of JUMP(palindromeID, character) →
palindromeID.
JUMP[palID][c] = nextPalID denotes that if we have palID palindrome id, then nextPalID is the suffix link of palID with maximum length that can be expanded with the character ‘c’.
This makes our algorithm as follows:
- See the new character and try expanding the largest suffix palindrome so far.
- If step 1 fails, then make a transition to suffix link JUMP (palID, c) where palID is largest suffix palindrome so far and c is newly encountered character.
We can see that the complexity here would be O(26 * N) since there are only 26 possible characters and total number of distinct palindromes are of the order of N.
Generating the JUMP transition table is quite simple. Notice that JUMP[i][1…26] is same as JUMP[suffixLink(i)][1…26] except for only one value i.e JUMP[i][c] where ‘c’ is the prefix character of suffixLink(i).
NOTE : The total number of distinct palindromes in a tree considering all paths u to v are bound by N ^ {3/2}. Since we are considering only paths from 1 to u, it would be much less.