|
|
back to boardany hint? in addition to using manacher to find palindrome length, is there any data structure that needs to be used? Re: any hint? 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 |
|
|