Re^2: Find common prefix from a list of strings

[AnomalousMonk]

c:\@Work\Perl\monks\Albannach>perl -wMstrict -le
"sub insert {
   my $trie=shift;
   my $str=shift;
   $trie=$trie->{$_}||={}
     foreach (split //,$str);
 }
 ;;
 sub common {
   my $trie=shift;
   my $common=\"\";
   while (1==scalar keys %$trie) {
       my $char=(keys %$trie)[0];
       $common.=$char;
       $trie=$trie->{$char};
   }
   $common;
 }
 ;;
 my %trie;
 insert(\%trie,$_) foreach qw(a ab abc);
 print common(\%trie);
"
abc

Shouldn't  'a' be the longest common prefix?

[demerphq]

Yeah. We have to track the end position and stop accordingly. A simple fix is to use the '' slot in the hash to hold "end state" data for the trie. Eg:

sub insert {
   my $trie=shift;
   my $str=shift;
   $trie=$trie->{$_}||={}
     foreach (split //,$str);
   $trie->{''}= $str;
 }

 sub common {
   my $trie=shift;
   my $common="";
   while (!exists($trie->{''}) and 1==scalar keys %$trie) {
       my $char=(keys %$trie)[0];
       $common.=$char;
       $trie=$trie->{$char};
   }
   $common;
 }

my %trie;
insert(\%trie,$_) foreach qw(a ab abc);
print common(\%trie);

Sorry it took so long to reply.