my %data;
$data{A} = [qw(a data goes here)];
$data{B} = [qw(b data here too)];
$data{C} = [qw(and here is c data)];
[download]

For example, here's a quick way to invert the index, and figure out which elements each item is in (presuming simple keys):

my %seen_in;
for my $key (sort keys %data) {
  for my $value (values %{$data{$key}}) {
    $seen_in{$value} .= $key;
  }
}
[download]

use Data::Dumper;

my @arA = qw( lion tiger dog cat snake);
my @arB = qw( tiger dragon lion);
my @arC = qw(dog phoenix);

my %all;
   @all{@arA} = ();

for (@arB) {
    next unless exists $all{$_};
    push @{$all{$_}}, "$_ - from array B";
}

for (@arC) {
    next unless exists $all{$_};
    push @{$all{$_}}, "$_ - from array C";
}

print Dumper \%all;
[download]

It would be easy to make this extensible (for arrays D, E, F, etc) if @arB, @arC were named like @{$arrays{B}} and @{$arrays{C}}. I'll leave that to you.

First of all, you can take the duplicated foreach my $elA (@arA) { ... } loops and combine them into one:

foreach my $elA (@arA) {
    foreach my $elB (@arB) {
        if ($elA eq $elB) {
            push @{$all{$elA}}, $elB." - from Array B";
        }
    }
    foreach my $elC (@arC) {
        if ($elA eq $elC) {
            push @{$all{$elA}}, $elC ." - from Array C";
        }
    }
}
[download]

Then, simplifying each inner loop would give you:

foreach my $elA (@arA) {
    map { ($elA eq $_) and push @{$all{$elA}}, "$_ - from Array B" } @
+arB;
    map { ($elA eq $_) and push @{$all{$elA}}, "$_ - from Array C" } @
+arC;
}
[download]

And finally, if you want to get really fancy, you could abstract even further (and anticipate adding other arrays into the mix):

#!/usr/bin/perl -w

use strict;
use warnings;
use Data::Dumper;

my @arA = qw( lion tiger dog cat snake );
my @arB = qw( tiger dragon lion );
my @arC = qw( dog phoenix );

my %all;

# This is the list of arrays we want to compare against "arA",
# where the key is the label, and the value is the corresponding
# array reference.
my $p = {
    'from Array B' => \@arB,
    'from Array C' => \@arC,
};

foreach my $elA (@arA) {
    foreach my $lbl (keys %$p) {
        map { ($elA eq $_) and push @{$all{$elA}}, "$_ - $lbl" } @{$p-
+>{$lbl}};
    }
}

print Dumper %all;
# Then do some other things with %all...
[download]

I think that's about as concise as you'll get it.

You may find List::Compare helps, but I can't help thinking there is a bit of XY going on here. What is the bigger problem you are trying to solve?

A cleaner and easier to maintain version of your sample code is:

use strict;
use warnings;
use Data::Dumper;

my @arA = qw(lion tiger dog cat snake);
my @arB = qw(tiger dragon lion);
my @arC = qw(dog phoenix);
my @arD = qw(lion wolf mouse);

my %all;
my %arrays = (b => \@arB, c => \@arC, d => \@arD);
my %aElts;

@aElts{@arA} = (1) x @arA;

for my $array (keys %arrays) {
    for my $elt (@{$arrays{$array}}) {
        next unless $aElts{$elt};
        push @{$all{$elt}}, "from Array $array";
    }
}

print Dumper \%all;
[download]

Prints:

$VAR1 = {
          'lion' => [
                      'from Array b',
                      'from Array d'
                    ],
          'dog' => [
                     'from Array c'
                   ],
          'tiger' => [
                       'from Array b'
                     ]
        };
[download]

You've got several very good responses. Now here's a craptacular bit of code:

#!/usr/bin/perl -w
use strict;
use warnings;

my @arA = ('alpha', 'beta', 'delta', 'omega');
my @arB = ('alpha', 'foo', 'bar', 'omega', 'baz', 'beta');
my @arC = ('delta', 'grond', 'floo', 'delta', 'omega');
my @all = ();

for my $elA (@arA) {
        my $idx=0;
        for my $elTest (@arB, @arC) {
                ++$idx;
                next unless $elA eq $elTest;

                if ($idx <= @arB) {
                        push @all, $elTest . " - from Array B";
                        next;
                }
                $idx -= @arB;

                if ($idx <= @arC) {
                        push @all, $elTest . " - from Array C";
                        next;
                }
                $idx -= @arC;

                # ... etc.
        }
}

print join("\n",@all);
[download]