Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Finding longest palindrome from a string

by William G. Davis (Friar)
on Aug 16, 2004 at 00:29 UTC ( #383160=note: print w/ replies, xml ) Need Help??


in reply to Finding longest palindrome from a string

All right, here's my attempt:

UPDATE: fixed it to account for "aba" palindromes, thanks BrowserUk:

UPDATE2: fixed again, thanks ccn:

#!/usr/bin/perl -w use strict; my $input = <STDIN>; chomp($input); my $longest_palindrome = ''; # look for two occurrences of the same character back to back or with +another # character in-between them to find palindromes: while ($input =~ /((.).?\2)/g) { # the first character beyond the three or two character middle of +a # palindrome: my $match_position = pos($input); # get the positions of the two matching characters: my $left_pos = $match_position - length $1; my $right_pos = $match_position - 1; # now go looking to the left and right of each matching character # for more matching characters: while (nextCharactersMatch($input, $left_pos, $right_pos)) { last if ($left_pos <= 0 or $right_pos >= length $input); $left_pos--; $right_pos++; } # extract the palindrome: my $offset = $left_pos; my $length = ($right_pos - $left_pos) + 1; my $palindrome = substr($input, $offset, $length); $longest_palindrome = $palindrome if ($length > length $longest_palindrome); # backtrack, to find palindromes within this palindrome: pos($input) -= (length($1) - 1); } print $longest_palindrome; sub nextCharactersMatch { my ($input, $left_pos, $right_pos) = @_; return 1 if (substr($input, $left_pos - 1, 1) eq substr($input, $right_pos + 1, 1)); }


Comment on Re: Finding longest palindrome from a string
Download Code
Re^2: Finding longest palindrome from a string
by BrowserUk (Pope) on Aug 16, 2004 at 00:53 UTC

    You don't appear to have catered for the 'aba' situation? Ie. Where the palindrome is symetrical around a single central character.


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re^2: Finding longest palindrome from a string
by ccn (Vicar) on Aug 16, 2004 at 08:46 UTC

    For bbabbbabbb your version outputs 7 chars bbbabbb instead of 9 chars bbabbbabb

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (16)
As of 2014-09-19 11:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (137 votes), past polls