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);