Gambit2007 Gambit2007 - 27 days ago 11
Perl Question

Perl - longest common prefix of 2 or more strings?

How can i create a Perl subroutine which would take in an array and find the longest common prefix for 2 or more of its elements? (strings)

I have this code:

sub longest_common_prefix {
$prefix = shift;
for (@_) {
chop $prefix while (! /^\Q$prefix\E/);
}
return $prefix;
}


But it only works if you are looking for the longest common prefix of all strings.

For example, if i pass an array with the following strings:

aaaBGFB
aaaJJJJ
jjfkBBB
aaaHGHG


I want it to return
aaa
as the answer.

Thanks!

Answer

One way would be to store the information in a hash. In this example, I set the hash key to the length of each prefix, and the value being the actual prefix found.

Note that this method overwrites a key and value if a same-length prefix exists, so you'll always get the last prefix found of the longest length (sort() takes care of finding the longest one).

The regex says "find the first character in the string and capture it, and use that char found in a second capture, and capture as many as there are". This string is then join()ed into a scalar and put into the hash.

use warnings;
use strict;

my %prefixes;

while (<DATA>){
    my $prefix = join '', /^(.)(\1+)/;
    $prefixes{length $prefix} = $prefix; 
}

my $longest = (sort {$b <=> $a} keys %prefixes)[0];
print "$prefixes{$longest}\n";

__DATA__
aaBGFB
aaaJJJJ
jjfkBBB
aaaHGHG

Output:

aaa
Comments