use strict; use Data::Dumper; my %result; { ### Populate initial tree my @prev; my %charcount; my $temp=; chomp $temp; foreach my $char (split '', $temp) { $charcount{$char}++; foreach my $pchar (@prev) { $result{$pchar}{$char.$charcount{$char}}{valid} = 1; }; push @prev, $char.$charcount{$char}; }; }; { ### Prune invalid data while () { chomp; my %charcount; my @invalid; foreach my $char (split '') { $charcount{$char}++; foreach my $ichar (@invalid) { $result{$char.$charcount{$char}}{$ichar}{valid} = 0; }; push @invalid, $char.$charcount{$char}; }; # Prune branches that weren't in the string this time around. foreach my $key1 (keys %result) { foreach my $key2 (keys %{$result{$key1}}) { my $found = 0; foreach my $inv (@invalid) { next if $found; $found = ($inv eq $key2); }; if (!$found) { $result{$key1}{$key2}{valid} = 0 }; }; }; # Prune roots that weren't in the string this time around. foreach my $key1 (keys %result) { my $found = 0; foreach my $inv (@invalid) { next if $found; $found = ($inv eq $key1); }; if (!$found) { foreach my $key2 (%{$result{$key1}}) { $result{$key1}{$key2}{valid} = 0; }; }; }; }; } my $maxdepthchar; { ### Determine depth of each tree my $maxdepth; foreach my $char (keys %result) { getdepth(\%result, $char); if ($result{$char}{depth} > $maxdepth) { $maxdepth = $result{$char}{depth}; $maxdepthchar = $char }; }; } { ### Output longest string while ($maxdepthchar ne '') { print substr($maxdepthchar,0,1); $maxdepthchar = @{$result{$maxdepthchar}{maxdepthchar}}->[0]; }; } sub getdepth{ my ($ref, $char) = @_; my %result = %{$ref}; my $maxdepth; my @maxdepthchar; if ($result{$char}{depth} eq undef) { foreach my $key (keys %{$result{$char}}) { if ($result{$char}{$key}{valid}) { my $depth = getdepth(\%result, $key); if ($depth > $maxdepth) { $maxdepth = $depth; @maxdepthchar = ($key) } elsif ($depth == $maxdepth) { $maxdepth = $depth; push @maxdepthchar, $key }; }; }; $result{$char}{depth} = $maxdepth+1; $result{$char}{maxdepthchar} = \@maxdepthchar; return $result{$char}{depth}; } else { return $result{$char}{depth}; }; }; __DATA__ HOUSEBOAT COMPUTER DOUBT