|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | checker failed | юри пустовалив | 1954. Пять палиндромов | 21 окт 2023 01:29 | 1 | admins, could you pls fix this? | any hint? | panyong0202 | 1954. Пять палиндромов | 1 авг 2018 11:02 | 3 | 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 | WA at test case 4 | sanjeevp | 1954. Пять палиндромов | 28 июн 2013 07:35 | 1 | Hi, Can someone please help with the type of test case 4. Thanks. |
|
|
|