<generalizing>
Do you need "a\$" and "^b"? That seems rather specific, and doesn't generalize. Perhaps "^a+\$" and "^b+\$" would be a better choice? Then it doesn't matter which one is processed first, or how many there are (e.g., "^c+\$").
</generalizing>

BTW, I like the $h{$_} .= "a" idea. To scale it much larger, I'd probably go with a bit vector, something like this:

my @AoA = ( [1..10], [2..11], [3..12] );
my %h;
foreach my $i ( 0..#@AoA ) {
    vec($h{$_},$i,1) = 1 for @{$AoA[$i]};
}
[download]

Of course, it's a bit more work to get the "only"s and "common"s out %(