Re: Find common prefix from a list of strings

Use a Trie.

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(model4run1 model2run1 model4run2 model1ru
+n1);
print common(\%trie);
[download]

But it could be argued I have Trie's on my brain. :-)

---
demerphq

_{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}

Comment on Re: Find common prefix from a list of strings Select or Download Code

Replies are listed 'Best First'.
Re^2: Find common prefix from a list of strings by AnomalousMonk (Archbishop) on Feb 24, 2014 at 17:42 UTC
`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?	[reply] [d/l] [select]
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]