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 SS and count the occurrences of each palindromes in the string. Now for a palindromic string of length nn to be Wavio Palindrome, it has to have a prefix (or suffix) of
length ⌈n2\frac{n}{2}⌉ which is also a palindrome.

From Palindromic tree we can see that, any node xx of length nn will be a Wavio Palindrome if it has a node of length ⌈n2\frac{n}{2}⌉ in its suffix link path towards root. The node need not be immediate suffix link of xx, it can be any node from link(x)link(x), link(link(x))link(link(x)), …, 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)xlink(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)O(n). Complexity of DFS part is also O(n)O(n) as there could be at most nn nodes in the tree. So the overall complexity of the solution is also O(n)O(n)



87% Solution Ratio
NirjhorEarliest, Dec '19
samiulsamiFastest, 0.0s
samiulsamiLightest, 136 kB
omar24Shortest, 1119B
Toph uses cookies. By continuing you agree to our Cookie Policy.