# Wavio Palindrome

The Tough Winter Spar, 20...

The intended solution for this problem was using Palindromic tree or Eertree. You can find tutorials on Palindromic tree here in Bangla or here in English.

Let's build a Palindromic tree on the given string $S$ and count the occurrences of each palindromes in the string. Now for a palindromic string of length $n$ to be Wavio Palindrome, it has to have a prefix (or suffix) of
length ⌈$\frac{n}{2}$⌉ which is also a palindrome.

From Palindromic tree we can see that, any node $x$ of length $n$ will be a Wavio Palindrome if it has a node of length ⌈$\frac{n}{2}$⌉ in its suffix link path towards root. The node need not be immediate suffix link of $x$, it can be any node from $link(x)$, $link(link(x))$, …, $link(x)$.

To check this build a new tree with all nodes from Palindromic tree (excluding -1 length node) and add edges from suffix link to every node. So an edge $link(x) \rightarrow x$ will be added. Now using a DFS on the new tree we can easily count the number of Wavio Palindromes.

The complexity of building Palindromic tree is $O(n)$. Complexity of DFS part is also $O(n)$ as there could be at most $n$ nodes in the tree. So the overall complexity of the solution is also $O(n)$

### Statistics

86% Solution Ratio
NirjhorEarliest, Dec '19
samiulsamiFastest, 0.0s
samiulsamiLightest, 136 kB
omar24Shortest, 1119B