Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Find common prefix from a list of strings

by demerphq (Chancellor)
on Jul 14, 2003 at 20:44 UTC ( #274157=note: print w/replies, xml ) Need Help??


in reply to 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);

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...

Replies are listed 'Best First'.
Re^2: Find common prefix from a list of strings
by AnomalousMonk (Bishop) 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

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

      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.

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://274157]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (7)
As of 2020-01-23 15:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?