Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

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

by demerphq (Chancellor)
on Apr 11, 2016 at 18:11 UTC ( #1160142=note: print w/replies, xml ) Need Help??


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

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://1160142]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2020-09-24 09:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If at first I donít succeed, I Ö










    Results (132 votes). Check out past polls.

    Notices?