http://www.spoj.pl/problems/EPALIN/
I use KMP. First generate failure function reverse of the string that given to me, then do KMP search to find largest suffix of the string that match with the prefix of the reverse string.
But I am not able to find anything wrong in my implementation. Can anybody please tell me why it's getting TLE??? Below is my cpp source code:
Edit: Got AC
You've just need to find Prefix function of last character of string rstr + # + str, let it be PR, and then output str and first len - PR chars of str in reverse order.
Could you please explain little bit more??? I didn't get your point :(
Let's make string s = rstr + # + str, where str is given string, rstr is reversed str. You can take every char on the place of "#", the main thing that this char was not in str. Then compute prefix function of it, then we just need take last value PR in array, this number will show length of the longest suffix of str, which is palindromic. One can prove it. Next step of algorithm is obvious: output str and first len - PR in reverse order as I alredy said.
Thank you very much. Now I got AC :)
I'm happy to help :)
I have also used same logic as described by you but still I am getting WA for EPALIN. Here is my source code: http://pastebin.com/HanhzYZs Do you find any flaw in it ?
Hey I'm using the same logic. Where are we going wrong ?
AC.. A slight mistake ! Debugging was fun
help... getting WA any corner cases.... https://ideone.com/EknGW8
thanku