in reply to Re: Find common prefix from a list of strings
in thread Find common prefix from a list of strings

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

[download]

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

Replies are listed 'Best First'.
Re^3: Find common prefix from a list of strings
by demerphq (Chancellor) on Apr 11, 2016 at 18:11 UTC

    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);

    [download]

    Sorry it took so long to reply.

    ---
    $world=~s/war/peace/g

[reply]
[d/l]

In Section Seekers of Perl Wisdom