comment on

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

In reply to Re^3: Find common prefix from a list of strings by demerphq
in thread Find common prefix from a list of strings by Albannach

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or or How to display code and escape characters are good places to start.


XP is just a number
	PerlMonks