Longest Palindrome by Regex

A few hours ago colomon blogged a Perl 6 solution to the longest palindrome programming challenge. It was a bit slow.

An all-regex solution looks like this:

for $string.match(:g, /(\w+) \w? <{ $0.flip }> /) {
    # process palindrome match here
    # filter out the longest match
}

It's also very slow, and it's very wasteful. So, can there be a hybrid between manual search a regex?

The regex engine is quite fast, and using it to find the center of a palindrome is a good starting point. From there on we can can move to both sides, and compare character by character if moving away from the match still results in a palindrome:

my $s = 'Fourscoreandsevenyearsagoourfaathers...';

my $solution;
my $longest = 0;
for $s.match(:g, /(\w)\w?$0/) {
    # $_ now holds a Match object,
    my $left = .from - 1;
    my $right = .to;

    # go to left and right while palindromic
    while $s.substr($left, 1) eq $s.substr($right, 1) {
        $left--;
        $right++;
    }

    # we move a bit too far
    $left++;
    $right;

    # and we're only interested in the longest
    # palindromic substring
    my $len = $right - $left;
    if $len > $longest {
        $solution = $s.substr($left, $right - $left);
        $longest = $len;
    }
}
say $solution;

This now runs in under 1.5 seconds on the 1169 characters long example input string.