Using a hash as a lookup table you end up iterating over @array_1 once (creating the hash), and the indices of @array_2 once. That's O(m+n)

my @Array_1 = ("a1","a2","a3","a4","a5","a6");
my @Array_2 = ("a1","b2","c3","a4","f5","a6");
my @Array_3 = ("1","2","3","4","5","6");

my %crossref;
@crossref{@array_1} = ();
my( @result_2, @result_3 );
foreach my $ix ( 0 .. $#array_2 ) {
    next if ! exists $crossref{$array_2[$ix]};
    push @result_2, $array_2[$ix];
    push @result_3, $array_3[$ix];
}
[download]