Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Try this in Regexp palindrome

by Anonymous Monk
on Mar 21, 2005 at 10:03 UTC ( [id://441160]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi monks,

Please help me the code. I am having the string = "abcdegedfc". Here, i have to find the palindrome from the string and removed the remainder text. This code has to performed only in regular expression i want this code output in one line expression.
Thanks in Advance.

Replies are listed 'Best First'.
Re: Try this in Regexp palindrome
by Random_Walk (Prior) on Mar 21, 2005 at 12:16 UTC
Re: Try this in Regexp palindrome
by bart (Canon) on Mar 21, 2005 at 11:13 UTC
    Using a delayed execution assertion, typically used to create recursively matching regexes, I came up with this:
    my $re; $re = qr/((.)(??{ $re })\2|.)/; my $s = 'abcdegedfc'; foreach my $i (0 .. length($s) - 1) { local $\ = "\n"; # add newline to print substr($s, $i) =~ /^$re/ and print $1; }
    I need a loop, because the regex by itself doesn't search for the longest palindrome, so I added a /^/ anchor to avoid any potential, useless backtacking. It doesn't actually chnage the result.

    This little program prints:

    a
    b
    c
    deged
    ege
    g
    e
    d
    f
    c
    
    So all you still have to do, is keep the longest match from the loops.

    update: I found a second working regex, inspired by holli who came up with the idea to use reverse:

    my $s = 'abcdegedfc'; foreach my $i (0 .. length($s) - 1) { local $\ = "\n"; # add newline to print substr($s, $i) =~ /((.*).?(??{ quotemeta reverse $2 }))/ and print $1; }
    Output is identical to the previous program.
      Your delayed-evaluation expression isn't quite right. It won't match palindromes like 'feef' that don't have a central character. You need to make the single dot optional. And if you put the alternation in the middle, you won't match one-character "palindromes".

      You can also simplify your search by putting the pattern in a lookahead and doing a while-global match:

      $_ = 'abcdegedfc'; # Try it without the g, too. my $re; $re = qr/((.)(?:(??{$re})|.?)\2)/; print "$1\n" while (/(?=$re)/g);
      If you change the * to a + in the reverse version, you exclude single-character palindromes. The lookahead while-global trick helps here, too:
      $_ = 'abcdegedfc'; print "$1\n" while (/(?=((.+).?(??{quotemeta reverse $2})))/g);

      Caution: Contents may have been coded under pressure.
        Your delayed-evaluation expression isn't quite right. It won't match palindromes like 'feef' that don't have a central character. You need to make the single dot optional.
        You're right. I knew that, and I still forgot about it. Thanks for the correction.
Re: Try this in Regexp palindrome
by rev_1318 (Chaplain) on Mar 21, 2005 at 10:59 UTC
    This code has to performed only in regular expression...

    Sorry, but put like that it really sounds like homework....
    Why the restriction?

Re: Try this in Regexp palindrome
by inman (Curate) on Mar 21, 2005 at 11:23 UTC
    The definition of a palindrome is a piece of text that can be read both forwards and backwards. Punctuation and whitespace is ignored. Case is also ignored.

    The base regexp for a potential midpoint is /(.).?\1/. The problem is that a single piece of input may contain multiple palindromic fragments in a larger palindrome. You will therefore need to test all midpoints.

    The code below creates a series of regular expressions that increasingly match longer palindromes.

    #! /usr/bin/perl -w use strict; use warnings; my $data = shift; $data =~ s/\W//g; my @groups; my @refs; for (1 .. (length $data) / 2) { push @groups, "(.)"; unshift @refs, "\\$_"; my $regex = join('',@groups).".?".join('',@refs); print "$regex\n"; while ($data =~ /$regex/ig) { print "$&\n"; } }

    The above code needs to run within the limits of the total number of matches that are available in the Perl regex engine.

    This regular expression looks simpler but uses in pattern code execution which is not supported across all regex engines (but it is in Perl so you will be OK). /(.*).?(?{reverse($1)})/.

    A hybrid approach would be to locate the midpoint using the /(.).?\1/ regex and then compare the leading part and the reverse of the trailing parts.

Re: Try this in Regexp palindrome
by Anonymous Monk on Mar 21, 2005 at 10:33 UTC
    use Regexp::Common; s/.*?($RE{lingua}{palindrome}).*/$1/s;
    Note that it will leave just the 'a' from your example string, as it will find the longest, left-most palindrome in the string. Which in this case is the string 'a'.
      For me, it always matches one character; it never matches a nontrivial palindrome.
      use Regexp::Common; $_ = 'abcdegedfc'; while (/($RE{lingua}{palindrome})/g) { print "Got $1\n"; } __END__ Got a Got b Got c Got d Got e Got g Got e Got d Got f Got c

      Caution: Contents may have been coded under pressure.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://441160]
Approved by Joost
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (6)
As of 2024-03-28 22:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found