but it will be typecasted int64 since res is int64…or not?
and one c[i] is just to manange new line
@mugurelionut @nims11 : I have seen hashing being used for string related problems many times, but never understood how its being implemented to solve such problems. Can you provide a brief overview of the concept used in this problem and how hashing is used coupled with a binary search ? (or a link to something similar where this has been explained?)
No, it’s not casted to long long if result is big enought, result type is depends on arguments if those are ints, result is int.
1 Like
@mugurelionut : hi,could you please explain your approach in detail,how exactly you are applying hashing ?
But I have handle them too in this part :-
int l = i - 1 - P[i];
l = l/2 - 1;
int r = i+1+P[i];
r = r/2 - 1;
Or could you tell me a test case where my code gives a WA?
@sandeepandey: In this problem hashing is used to check if a substring of the given string is a palindrome. Let’s say we have the substring from position i to position j. Then we compute a hash h1 for the substring from i to j and a hash h2 for the reverse substring from j to i. If h1=h2 then we can assume that the string from i to j is a palindrome (of course, we could be wrong, but it very unlikely if the hash function is good). The important part is to be able to compute such hashes in O(1) time (after some initial preprocessing).
2 Likes
Ok, here is a test case
1
5
a 1
b 1
a 1
b 1
a 1
@mugurelionut: Thankyou. I understood your idea of using hashing.Thats pretty cool.but still i dont understand why you are using Binary Search here ?
I would like to clarify about somethings. 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: http://www.codechef.com/viewsolution/2400280
P[i]++ should be moved to end of loop.
@utkarsh Thx for that … I saw that mistake n changed the code to
http://www.codechef.com/viewsolution/2400905
but it still gives me WA. Can you plz give me a test case where it fails?
Thx for the repliers … I totally understood the question n solved it correctly 
Manacher’s is in my mind now 
I tried my code with thousands of different inputs and it always gave the exact same answer as successful submissions, but I get WA. I wonder if someone can point me to any test case where my code fails. https://www.codechef.com/viewsolution/12275159
As per my understanding, we can solve this problem by writing a c program trying to find longest palindrome string centered at a character. Let the center character is ‘x’, then we will move in both direction of x and check if this sub string or not. IF we find that it is not a palindrome string then we can stop further scan and jump to next adjacent character in the given string. I donno how to write correct program for this … but this algorithm looks good to me.