Be careful when you implement Manacher's algorithm, when you copy the ready part for the second part, don't forget making all the needed changes, I forgot changing just one sign !