|
|
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. |
|
|
