Originally Posted by

**fifthrapiers** Hello; I have this question regarding an algorithm. CaptainBlack, in particular, if you have some time mind giving it a shot, as last time you were able to help me with another algorithm. Thanks!

"22.7 Maximal palindromes

A palindrome is a string that reads the same forwards as backwards, such as axbccbxa.A substring U of a string S is a maximal palindrome if and only if it is a palindrome and extending it onecharacter in both directions yields a string that is not a palindrome. Generally we separate even-length maximalpalindromes, or even palindromes for short, and odd-length maximal palindromes (odd palindromes) for convenience. For example, in S = axbccbbbaa, the maximal even palindromes are bccb,bb, and aa. The string bbb isa maximal odd palindrome, and we will skip writing the maximal odd palindromes of length 1. Note that everypalindrome is contained in a maximal palindrome.

(Below is an algorithm for finding the even-length palindromes of S; suppose length of S= n).

Here is a simple way to find all even-length maximal palindromes in linear time. (Finding odd-length maximal palindromes is similar.)

Consider S$ and S^r#, the reversal of S. There is a palindrome of length 2k with the middle just after position q ifthe string of length k starting from position q+1 of S matches the string of length k starting from position n−q+1of S^r#. In particular, this palindrome will be maximal if this is the length of the longest match from these positions.Thus, solving the even-length maximal palindrome problem corresponds to computing the longest commonextension of (q+1,n−q+1) for all possible q."

QUESTIONS:

1.) How do we change the above algorithm so that it finds odd-length palindromes?