[FEATURE REQUEST] <title>Add a new Algorithm Manacher’s Algorithm

[Abhinavagarwa]

What would you like to Propose?

Here's an algorithm that is not listed in the structure you provided: "Manacher's Algorithm", which is used to find the longest palindromic substring in linear time.

Algorithm: Manacher’s Algorithm
Purpose:
Given a string s, the algorithm finds the longest palindromic substring in linear time (O(n)).

Issue details

Preprocess the string:

Insert special characters (like #) between each character of the original string and add ^ at the beginning and $ at the end to avoid boundary conditions. This turns any even-length palindrome into an odd-length one.
Example: "abba" becomes "^#a#b#b#a#$".
Initialize Variables:

P[]: An array where P[i] stores the radius of the palindrome centered at position i.
C: The center of the current palindrome.
R: The right boundary of the current palindrome.
Iterate Over the String:

For each character in the transformed string:
Mirror the palindrome from the left side if the current index is within the bounds of the current palindrome.
Try expanding the palindrome centered at the current character.
Update the center C and the right boundary R if the palindrome expands beyond the current boundary.
Return the Result:

The longest palindrome found will be the one with the maximum value in P[]. Use this to find the center and reconstruct the longest palindromic substring from the original string.

Additional Information

No response

[SAIVARDHAN15]

hey @Abhinavagarwa, can I work on this algo?