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."
1.) How do we change the above algorithm so that it finds odd-length palindromes?
2.) Using both the even algorithm and the one you come up with in 1, find all of the even and odd palindromes of the following string: c b a a b a
3.) Consider MISSISSIPPI$ and IPPISSISSIM#; if we were to run both of the algorithms, list each of the q's and the palindrome(s) that we'd get for that q. (Note: we may not get any palindromes for a specific q, if so then say 'none'.
4.) In fact, we do not get all palindromes of a string. What type of palindromes do we end up getting?