Manacher's Algorithm in Java

Manacher's Algorithm is a well-known approach for determining the longest palindromic substring within a given string. It was introduced by Glenn K. Manacher in 1975. The Algorithm uses the concept of palindrome symmetry to reduce the number of comparisons required to find the longest palindromic substring.

Manacher's Algorithm is a highly effective method for identifying the longest palindromic substring within a given string. It works by taking advantage of the symmetry property of palindromes.

Example

Suppose we have the string "abaxabaxabb". We can create a new string by inserting a "#" character between each pair of characters: "a#b#a#x#a#b#a#x#a#b#b#". Then we can apply Manacher's Algorithm as follows:

1. Initialize center = 0 and right = 0.
2. Initialize p to [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
3. Loop through each position i in the new string:
   1. At i = 0, p[0] = 0.
   2. At i = 1, p[1] = 1, center = 1, right = 2.
   3. At i = 2, p[2] = 0.
   4. At i = 3, p[3] = 3, center = 3, right = 6.
   5. At i = 4, p[4] = 0.
   6. At i = 5, p[5] = 1, center = 3, right = 6.
   7. At i = 6, p[6] = 0.
   8. At i = 7, p[7] = 1, center = 7, right = 8.
   9. At i = 8, p[8] = 0.
   10. At i = 9, p[9] = 1, center = 7, right = 10.
   11. At i = 10, p[10] = 2, center = 10, right = 12.
   12. At i = 11, p[11] = 0.
   13. At i = 12, p[12] = 1, center = 10, right = 14.
   14. At i = 13, p[13] = 0.
   15. At i = 14, p[14] = 1, center = 14, right = 16.
   16. At i = 15, p[15] = 0.
   17. At i = 16, p[16] = 1, center = 14, right = 18.
   18. At i = 17, p[17] = 0.
   19. At i = 18, p[18] = 0.
   20. At i = 19, p[19] = 0.
   21. At i = 20, p[20] = 0.
   22. At i = 21, p[21] = 0.
   23. At i = 22, p[22] = 0.
   24. At i = 23, p[23] = 0.
   25. At i = 24, p[24] = 0.
   26. At i = 25, p[25] = 0.
4. Find the index of the maximum value in p, which is 14. The longest palindromic substring in the new string is "a#b#a#x#a#b#a#x#a#b#a", which corresponds to the original string "abaxabaxaba". Since the "#" characters were only added for the algorithm, we can remove them and get the original palindrome.

Algorithm

1. Create a new string by inserting a special character (such as #) between each pair of characters in the original string. It ensures that every palindrome in the new string has an odd length.
2. Initialize two variables: Center and right. The Center represents the Center of the palindrome we have found so far, and the right represents the rightmost boundary of this palindrome.
3. Initialize an array p to store the length of the palindrome centered at each position in the new string. Initially, set all elements to zero.
4. Loop through each position in the new string. At each position i, do the following: a. If i is less than right, set p[i] to the minimum of p[2 * center - i] and right - i. We can reuse information from previously discovered palindromes to avoid redundant work. b. Expand the palindrome centered at i as far as possible, updating p[i] accordingly. c. If the right boundary of this palindrome extends beyond the current value of the right, update the Center and right accordingly.
5. Find the index of the maximum value in p. It represents the Center of the longest palindrome in the new string.
6. Use the Center and the palindrome length to extract the corresponding substring from the original string.

Implementation

Filename: ManachersAlgorithm.java

Output:

baxabaxab 

Complexity Analysis: The time complexity of the Manacher's Algorithm for finding the longest palindromic substring in a string of length n is O(n). It is because the algorithm processes each character in the string only once and performs constant time operations for each character.

The space complexity of the algorithm is O(n) as well. It is because the algorithm uses an array of length n to store the palindrome lengths and a StringBuilder object of length 2n+1 to modify the input string.