Implementation of Manacher's algorithm to find Longest Palindromic Substring in O(N)

[mdrpanwar]

Is your feature request related to a problem? Please describe.
The existing implementation of Longest Palindromic Substring algorithm at /Strings/LongestPalindromicSubstring is O(N^3). Faster algorithms for this task are known to exist.

Describe the solution you'd like
I would like to add Manacher's algorithm which finds Longest Palindromic Substring in O(N).

Additional context
Here is the link to the Wikipedia page of Longest palindromic substring which mentions Manacher's algorithm.

I would like to work on this implementation as part of Hacktoberfest 2021.

@siriak Could you please assign this issue to me? Also, should I add this to a new file?

Thanks.

[siriak]

Yes, to a new file

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions]

Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!