|
|
Does anyone know what this could be related to? I found the following test when got WA4: INPUT: aaa OUTPUT: 4 Use Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays: beg[i] - number of palindroms begins at position i, end[i] - number of palindroms ends at position i. after that ans = beg[i + 1] * end[i] for every i. To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures. Edited by author 22.05.2017 20:40 My algo is right. Now i have AC. My problem is input string. I rewrite my program on Pascal (i use ANSISTRING) and got AC. Edited by author 21.08.2016 18:31 Sorry to blunt, but I don't understand the meaning of the task. Explain what needs to be done. Examples of chewing the tasks: abaa 1. i = 1, j = 1, k = 2; ' a ' and ' b ' palindromes 2. i = 1, j = 3, k = 4; ' aba ' and ' a ' palindromes 3. i = 2, j = 2, k = 3; ' b ' and ' a ' palindromes 4. i = 2, j = 2, k = 4; ' b ' and ' aa ' palindromes 5. i = 3, j = 3, k = 4; ' a ' and ' a ' palindromes Russian text: Разжевывание примера из задачи: abaa 1. i=1, j=1, k=2; 'a' и 'b' палиндромы 2. i=1, j=3, k=4; 'aba' и 'a' палиндромы 3. i=2, j=2, k=3; 'b' и 'a' палиндромы 4. i=2, j=2, k=4; 'b' и 'aa' палиндромы 5. i=3, j=3, k=4; 'a' и 'a' палиндромы you can use Manacher's algorithm. |
|
|