Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

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.


Log In?

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2022-01-21 18:37 GMT
Find Nodes?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:

    Results (59 votes). Check out past polls.