Wavio Palindrome

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)$