in addition to using manacher to find palindrome length, is there any data structure that needs to be used?

I don't know whether is can be solved with Manacher's algorithm but I've easily ACed with Palindromic tree (sometimes called eertree).

You should find minimum odd length factorization of a word. Then you have four cases:
1) If this length is equal to one, i.e. the word is a palindrome, then you output first two letters, substring starting from the third letter without last two characters and finally last two characters.
2) If the length is 3 then you find any subpalindrome of length >= 3 and split it into three palindromes (just like splitting one palindrome into 5 in the previous step)
3) If the length is 5 then just backtrack the answer with dynamic programming (you also need it for the second case)
4) If it is greater than 5 (>= 7) then output "NO".

Edited by author 29.07.2018 12:34

Edited by author 29.07.2018 12:34

thank you