Problems? Is your data what you think it is? 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@/

Create A New User
Domain Nodelet?
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 chilling in the Monastery: (3)
As of 2021-09-21 10:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?