Let's build a Palindromic tree on the given string and count the occurrences of each palindromes in the string. Now for a palindromic string of length to be Wavio Palindrome, it has to have a prefix (or suffix) of
length ⌈⌉ which is also a palindrome.
From Palindromic tree we can see that, any node of length will be a Wavio Palindrome if it has a node of length ⌈⌉ in its suffix link path towards root. The node need not be immediate suffix link of , it can be any node from , , …, .
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 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 . Complexity of DFS part is also as there could be at most nodes in the tree. So the overall complexity of the solution is also