I would like to clarify about somethings about Counting all palindromic substrings in Short Contest. I know that we have to calculate the number of palindromic substrings centered at each letter. Here is what I did but it still gives me wrong answer.
Assume A[i] is a pair or char and long long after adding (#, 0) between the letters.
1- For each A[i] init P[i] = 0. (This means am not using the symmetry property)
2- init V[i] = A[i].Y * (A[i].Y + 1) / 2;
3- while I can still expand this palindrome I wrote this code:
while(A[i - P[i] - 1].X == A[i + P[i] + 1].X) {
P[i]++;
V[i] += min(A[i - P[i] - 1].Y, A[i + P[i] + 1].Y);
if(A[i - P[i] - 1].Y != A[i + P[i] + 1].Y) {
break;
}
}
4- When manacher’s algorithm is over I add all the values of V[i] to get the final result. What is wrong with this way? Why is it giving me a wrong answer. If you’d like to have a look at the full code here it is: CodeChef: Practical coding for everyone