Palindromes

Definitions:

1. Palindrome: A string that reads the same forward and backward.

   • Even Palindrome \(p_P\): If a palindrome can be expressed as \(p_P = ww^R\), where \(w\) is a substring and \(w^R\) is its reversed string, it is called an even palindrome.
   • Odd Palindrome \(p_N\): If a palindrome can be expressed as \(p_N = wXw^R\), where \(w\) is a substring and \(X\) is any character from the alphabet, it is called an odd palindrome.

2. Maximal Palindrome: A palindrome in a string is maximal if it cannot be extended by including adjacent characters on either side without breaking the palindrome property.

Task:

Implement a function that identifies all such maximal palindromes within a provided string. These palindromes should be returned as a list of pairs:

• Each pair \(i, d)\) should denote that there is a palindrome starting at index \(i\) of length \(d\) in the original string.
• The function should work in linear time relative to the length of the string.

Manacher's Algorithm Overview:

Manacher's algorithm processes the string to find the longest palindromes centered at each character efficiently:

• Transformation: The input string is transformed by inserting a special character (usually #) between each pair of characters and adding sentinel characters (^ and $) at the beginning and end to avoid bounds checking.
• Palindromic Length Array: An array where each position \(i\) indicates the radius (half the length) of the largest palindrome centered at position \(i\) in the transformed string.
• Center and Right Boundary: While iterating through the string, if a position \(i\) is within the current known right boundary of a palindrome, the algorithm uses previously computed values to potentially avoid some computations.

Output:

The output should be a list of tuples:

• Each tuple represents a palindrome in the original string where the first element is the starting index of the palindrome and the second element is its length.
• Only palindromes of length at least 2 are considered valid output.

Additional Information:

• Special characters like # and $ are used as guards in the transformation to simplify the bounds checking.
• Palindromes of both even and odd lengths are computed, but the function will consider both to give a complete list of maximal palindromes.

This method finds practical applications in fields like genetics (for finding palindromic sequences in DNA), text processing, and other areas where pattern recognition in sequences is required.