Codeforces Global Round 7 D2

Can somebody please tell me how to solve this problem. I have tried a lot to think but I am not able to think any solution better than O(n^2) here. I know it should be done in O(n). I read the editorial but could not understand it.
Here is the link to the problem: Problem - D2 - Codeforces

I just got to know that there is this thing called as the Manacher’s Algorithm. However, it is really hard to understand. Can somebody provide a good resource to study it or explain it here only?

I used this blog to edit manacher during contest time.

You need one line change in the condition of the code in the hackerearth blog for AC in D2.

Thanks and I know the change, i need to check if the middle_point-max_length/2==left_most point or not.
Thanks for the link to the material by the way.

1 Like