ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1954. Five Palindromes

any hint?
Posted by panyong0202 29 Jul 2018 04:53
in addition to using manacher to find palindrome length, is there any data structure that needs to be used?
Re: any hint?
Posted by die_young 29 Jul 2018 12:20
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
Re: any hint?
Posted by panyong0202 1 Aug 2018 11:02
thank you