Thread: Algorithms!

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?

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?

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?

This should do the job (though messing with these indicies is tricky).

Consider S$ and S^r#, the reversal of S. There is a palindrome of length 2k+1 with the middle at position q if the string of length k starting from position q+1 of S matches the string of length k starting from position n−q+2of S^r#.

RonL

(note: my first go at this had to be modified in the light of what the actual code
did, when I cam to run it)

Originally Posted by fifthrapiers

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

The following functions implement the algorithms (as far as I can tell)
(note I am working with numerical arrays rather than strings as it is
easier to implement quickly)

(code written so quickly comes with no guarantee of correctness )

Code:

function Epalind(s)
##
##  find even palindromes in s
##
##
  n=length(s);
  sr=s(n:-1:1);
  for q=1 to n
    mxk=min(n-q,q-1);
    for k=1 to mxk
      s1=s(q+1:q+k);
      s2=sr(n-q+1:n-q+k);
      if prod(s1==s2)==1
        s(q-k+1:q+k)
      endif
    end
  end
  return 0
endfunction
 
..======================================
 
function Opalind(s)
##
##  fid odd palindromes in s
##
  n=length(s);
  sr=s(n:-1:1);
  for q=1 to n
    mxk=min(n-q,q-1);
    for k=1 to mxk
      s1=s(q+1:q+k);
      s2=sr(n-q+2:n-q+k+1);
      if prod(s1==s2)==1
        s(q-k:q+k)
      endif
    end
  end
  return 0
endfunction

Results are:

Code:

 
>
>s=[3,2,1,1,2,1];
>Epalind(s);
            1             1 
            2             1             1             2 
>
>
>Opalind(s);
            1             2             1 
>

RonL

Originally Posted by fifthrapiers

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'.

Not quite theformat the question asks for (code modified to print
q and k):

Code:

 
>s=[13,9,19,19,9,19,19,9,16,16,9];
>
>
>Epalind(s)
q= 3    k= 1
  19   19 
 
q= 3    k= 2
   9   19   19    9 
 
q= 6    k= 1
  19   19 
 
q= 6    k= 2
   9   19   19    9 
 
q= 9    k= 1
  16   16 
 
q= 9    k= 2
   9   16   16    9 
 
   0 
>Opalind(s);
q= 5    k= 1
  19    9   19 
 
q= 5    k= 2
  19   19    9   19   19 
 
q= 5    k= 3
   9   19   19    9   19   19    9 
 
>

Originally Posted by fifthrapiers

4.) In fact, we do not get all palindromes of a string. What type of palindromes do we end up getting?

It might be a bug, but I dont pick up where the length of S is even and
S is a palindrome itself.

RonL