Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: Finding longest palindrome from a string

by fizbin (Chaplain)
on Aug 13, 2004 at 14:14 UTC ( #382680=note: print w/ replies, xml ) Need Help??


in reply to Finding longest palindrome from a string

Given the number who have gone before, surely this has been done already, but...


sub fizbin {
  return $_[0] unless ($_[0] and length($_[0]) > 1);
  my @string = (300, unpack("U*", $_[0]), 301);
  my $palstart, $palend;
  my ($bestlen, $beststart, $bestend) = (-1,-1,-1);
  for ($palmid = 1; $palmid < $#string; $palmid++)
  {
    if ($string[$palmid] == $string[$palmid+1])
    { # try even-length palindrome
      ($palstart, $palend) = ($palmid, $palmid+1);
      while ($string[$palend+1] == $string[$palstart-1])
      {
        $palend++; $palstart--;
      }
      if ($bestlen < $palend - $palstart)
      {
          ($bestlen, $bestend, $beststart) =
          ($palend - $palstart, $palend, $palstart);
      }
    }
    # try odd-length palindrome
    ($palstart, $palend) = ($palmid, $palmid);
    while ($string[$palend+1] == $string[$palstart-1])
    {
      $palend++; $palstart--;
    }
    if ($bestlen < $palend - $palstart)
    {
      ($bestlen, $bestend, $beststart) =
          ($palend - $palstart, $palend, $palstart);
    }
  }
  pack("U*", @string[$beststart..$bestend]);
}
It's also unfortunately an O(n^2) algorithm, but my initial O(n) idea turned out to be badly flawed. (Actually, I guess it's O(n*m), where "n" is the length of the input and "m" is the length of the longest palindrome - in the worst case, a string of all the same letter, it'd be O(n^2))

Note that it'll also work on unicode strings, assuming that perl knows that its argument is a unicode string.

-- @/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/


Comment on Re: Finding longest palindrome from a string
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://382680]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (14)
As of 2015-07-07 21:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (93 votes), past polls