### Problem Link

**Author**: Aditya Shah

**Tester**: Sai Sandeep

### Difficulty

Medium - Hard### Prerequisites

Palindromic Tree### Explanation

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 (**where*palID*,*c*)is largest suffix palindrome so far and**palID**is newly encountered character.**c**

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][**where ‘

*c*]*c*’ is the prefix character of

*(i).*

**suffixLink****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.