use Data::Dumper;
my $hoh = {};

   foreach my $str ('a:b:c:d:a','a:b:c:d:z'){      
      my @vals    = split /:/,$str;
      my $hr      = $hoh;
      my $lastkey = @vals[-2];

      for (0..$#vals-2){
         $hr->{$vals[$_]}= $hr->{$vals[$_]} || {};
         $hr=$hr->{$vals[$_]};
      }
      if (defined $lastkey){
         push @{$hr->{$lastkey}}, [@vals[-1], $str];
      }
   }

print Dumper($hoh);

$VAR1 = {
          'a' => {
                   'b' => {
                            'c' => {
                                     'd' => [
                                              [
                                                'a',
                                                'a:b:c:d:a'
                                              ],
                                              [
                                                'z',
                                                'a:b:c:d:z'
                                              ]
                                            ]
                                   }
                          }
                 }
        };