for my $index (0 .. $#other_array) {
    push @{$lookup{$other_array[$index]}}, $index;
}
[download]

This will create a lookup hash that contains, as hash value, an array with every index in the other array where it has been found.

So, instead of having to search through the other array for every item, you now immediately have a list of where it was found, so you can jump straight into the action.

for my $item (@first_array) {
    if($lookup{$item}) {
        foreach my $where (@{$lookup{$item}}) {
            # ...
        }
    }
}
[download]

I have no idea what your exact data structures look like, but I'm sure you can adapt this idea to your code.