use Data::Dumper;

   my $foo = "a:b:c:d:a";
   my $bar = "a:b:c:d:z";
   my $hoh = {};
   sub createHash {
      my ($hoh,$orig,$rest,$last) = @_;
      $rest = $rest || $orig;
      $_ = $rest;
      if (/^(.*?):(.*)$/)
      { 
         $hoh->{$1} = $hoh->{$1} || {};
         createHash($hoh->{$1},$orig,$2,$1);
      } 
      elsif (defined($last)) 
      {
         push (@{$hoh->{$last}} , [$rest,$orig]);
      }
      return $hoh;
   }
   $hoh = createHash($hoh,$foo,undef);
   $hoh = createHash($hoh,$bar,undef);

   print Dumper($hoh);

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