Adventures in Palindromes
by William R. Mahoney

Figure 1:

Test the incoming string--if not a partial palindrome return False
If it is a complete palindrome
   Print it
   Return True
Else if the pivot is less than the center
   Take excess letters from the right side
   Reverse the letters
   For the length of these letters down to 1, do
      Locate the first dictionary word ending in these letters
      Use lazy binary search to do so
      While more words
         Create a new string by prefixing the dictionary word
         If recursive call returns true
            Return True
Else the pivot is greater than the center, so
   Take the excess letters from the left side
Reverse the letters
For the length of these letters down to 1, do
   Locate the first dictionary word starting with these letters
   Use lazy binary search to do so
   While more words
      Create a new string by appending the dictionary word
      If recursive call returns true
         Return True
Return False


Listing One

if ( bottom < top )
   mid = ( bottom + top ) / 2
   if ( dictionary[ middle ] < string )
      recursively search from mid + 1 to top
   else
      recursively search from bottom to mid
else
   if ( top < bottom )
      not found
   else
      found at bottom





1



