Let's take another approach:

What are you trying to achieve?

You want to know in what rows the letters (of the first row) occur? (although that's not quite correct) or ...?

As in, $answ_hoa1[1] (["B","B","-","B"]) tells you that the first row, the second row and the fourth row has the letter 'B'

But this is only true for $answ_hoa1[0] and $answ_hoa1[1]... But not for $answ_hoa1[3] and $answ_hoa1[4] probably because of rule 6, is this view correct?

Unless: if the match for the next letter may only start where the last one ended: example: it matches the B in the key2-array at the end, which means that it should start looking for the C and the D after the B (which is impossible since B is the end of the array)

Is the following input possible?:

 'key1' => ["A","B","C","D"],
 'key2' => ["A","C","B","C"],
 'key3' => ["C","A","D","H"],
 'key4' => ["A","B","I","C"],
[download]

[ "A", "A", "A", "A" ],
[ "B", "B", "-", "B" ],
[ "C", "C", "-", "C" ],
[ "D", "-", "D", "-" ],
[download]

Updated after reading tlm's code

Update2: code. This code does basiclly the same as tlm's code, except that his code modifies the hash (that is the arrays in the hash), and mine doesn't.

my @output = ();
my @keys = sort keys %hash;

my %start = ();
@start{@keys} = (0) x scalar(@keys);

my $first         = shift @keys;
my $total_columns = $# { $hash{$first} };

for my $column (0 .. $total_columns) {
  $output[$column] = [ $hash{$first}[$column] ];

  for my $hkey (@keys) {
    my $aref = $output[$column];
    push @$aref, "-";
    for my $i ($start{$hkey} .. $total_columns) {
      if ($aref->[0] eq $hash{$hkey}[$i]) {
        $aref->[-1] = $aref->[0];
        $start{$hkey} = $i + 1;
        last;
      }
    }
  }

}
[download]