($a & $b_mask) eq ($b & $a_mask)

##</code><code>##

  #    a   and mask[b]  eq      b   and mask[a]
  ($_[0][1] & $_[1][2]) eq ($_[1][1] & $_[0][2]);

##</code><code>##

Benchmark: timing 25000 iterations of cclever3, clever2, clever3, csimple3, simple3...
  cclever3:  1 wallclock secs ( 0.95 usr +  0.00 sys =  0.95 CPU) 
             @ 26315.79/s (n=25000)
   clever2: 10 wallclock secs ( 8.73 usr +  0.02 sys =  8.75 CPU) 
             @  2857.14/s (n=25000)
   clever3:  1 wallclock secs ( 1.15 usr +  0.00 sys =  1.15 CPU) 
             @ 21739.13/s (n=25000)
  csimple3:  1 wallclock secs ( 1.04 usr + -0.01 sys =  1.03 CPU) 
             @ 24271.84/s (n=25000)
   simple3:  5 wallclock secs ( 3.97 usr +  0.01 sys =  3.98 CPU) 
             @ 6281.41/s (n=25000)

##</code><code>##

#!/usr/bin/perl

use Benchmark;

# Remove the following paragraph and the benchmarks for csimple3 and
# cclever3 if you don't have Inline::C.
use Inline C => 'DATA',
  VERSION => 0.0,
  NAME => 'SimpleTest',
  OPTIMIZE => '-O3';
Inline->init;

sub simple3
{
  my($a,$b)=@_;
  my(@seen);

  return undef if (length($a) != length($b));
  foreach my $i (0..length($a))
  {
    my($ac,$bc)=(substr($a,$i,1),substr($b,$i,1));
    if ($ac eq $bc)
    {
      ; # Do nothing
    }
    elsif ($ac eq '_')
    {
      return undef if (++$seen[$bc] > 1);
    }
    elsif ($bc eq '_')
    {
      return undef if (++$seen[$ac] > 1);
    }
    else { return undef }
  }
  1;
}

# Represent each string as two strings and two masks.
sub clever2
{
  # Data transformations; could be done beforehand in linear time.
  # Underscores become \0 for easier masking and comparison
  (my $a = $_[0]) =~ tr/_/\0/;
  (my $b = $_[1]) =~ tr/_/\0/;

  # Compute a "transposed" string showing the position of each character,
  # leaving \0 if it doesn't appear.
  my($a3,$b3)=("\0"x10,"\0"x10);
  foreach my $i (0..(length($a)-1))
  {
    my $c = substr($a,$i,1);
    next if $c eq "\0";
    substr($a3,$c,1)=$i;
  }
  foreach my $i (0..(length($b)-1))
  {
    my $c = substr($b,$i,1);
    next if $c eq "\0";
    substr($b3,$c,1)=$i;
  }

  # Concatenate together
  my $a_new = $a . $a3;
  my $b_new = $b . $b3;

  # Compute the mask
  (my $a_mask = $a_new)  =~ tr/\0/\xff/c;
  (my $b_mask = $b_new)  =~ tr/\0/\xff/c;

  # Comparisons; must be done for each comparison.
  return (($a_new & $b_mask) eq ($b_new & $a_mask));
}

# Same as clever2, but with data structure precomputed.
sub clever3
{
  #    a   and mask[b]  eq      b   and mask[a] 
  ($_[0][1] & $_[1][2]) eq ($_[1][1] & $_[0][2]);
}

# Precompute the data structure for clever3
sub clever3_xform
{
  # Underscore to \0 for easier masking and comparison
  (my $a = $_[0]) =~ tr/_/\0/;

  # Compute a "transposed" string showing the position of each character,
  # leaving \0 if it doesn't appear.
  my($a3)="\0"x10;
  foreach my $i (0..(length($a)-1))
  {
    my $c = substr($a,$i,1);
    next if $c eq "\0";
    substr($a3,$c,1)=$i;
  }

  # Concatenate
  my $a_new = $a . $a3;

  # Calculate the mask
  (my $a_mask = $a_new)  =~ tr/\0/\xff/c;

  # Return an arrayref; this is the data structure we'll use in clever3.
  return [$_[0],$a_new,$a_mask];
}

my @tests =
(qw/
     _8__3__19
     48____7__

     _8__3__19
     4_2___7__

     _8__3__19
     4_8___7__

     __8_3__19
     48____7__

     __8_3__19
     84____7__

     _8__3__19
     48_____7_
   /
);

sub run_tests
{
  my($func,$verbose,@tests)=@_;
  my ($s1, $s2);
  while (defined($s1 = shift(@tests)))
  {
      $s2 = shift(@tests);
      my $result = $func->($s1, $s2);
      if ($verbose)
      {
        if (ref($s1) && ref($s2))
        {
          $s1 = $s1->[0];
          $s2 = $s2->[0];
        }
        print "$s1\n$s2: ",$result?"compatible":"not compatible","\n";
      }
  }
}

my @tests_clever3 = map { clever3_xform($_) } @tests;
run_tests(\&clever3, 1, @tests_clever3);

timethese(25_000, {
                 simple3 => sub { run_tests(\&simple3, 0, @tests) },
                 csimple3 => sub { run_tests(\&csimple3, 0, @tests) },
                 clever2 => sub { run_tests(\&clever2, 0, @tests) },
                 clever3 => sub { run_tests(\&clever3, 0, @tests_clever3) },
                 cclever3 => sub { run_tests(\&cclever3, 0, @tests_clever3) },
                });


__DATA__
__C__
int csimple3(const char *a, const char *b)
{
  int i;
  int l;
  unsigned char seen[256];

  memset(seen,0,256);

  if ((l=strlen(a)) != strlen(b))
    return 0;
  for(i=0;i<l;i++)
  {
    if (a[i] == b[i])
    {
      ; /* Do nothing */
    }
    else if (a[i] == '_')
    {
      if (++seen[b[i]] > 1)
        return 0;
    }
    else if (b[i] == '_')
    {
      if (++seen[a[i]] > 1)
        return 0;
    }
    else
      return 0;
  }
  return 1;
}

int cclever3(SV *a, SV *b)
{
  AV *a_arr, *b_arr;
  SV **tmp;
  char *a_val, *a_mask, *b_val, *b_mask;
  int i;
  
  /* First  get the arrays from the references */
  if (!SvROK(a) || !SvROK(b))
    croak("a or b not arrayrefs!");
  a_arr = (AV*)SvRV(a);
  b_arr = (AV*)SvRV(b);

  /* Now pull out the data */

  if ( (tmp = av_fetch(a_arr, 1, 0)) == NULL)
    croak("a[1] is undef");
  if ((a_val = SvPV(*tmp, PL_na)) == NULL)
    croak("a[1] contains NULL pointer?");

  if ( (tmp = av_fetch(a_arr, 2, 0)) == NULL)
    croak("a[2] is undef");
  if ((a_mask = SvPV(*tmp, PL_na)) == NULL)
    croak("a[2] contains NULL pointer?");


  if ( (tmp = av_fetch(b_arr, 1, 0)) == NULL)
    croak("b[1] is undef");
  if ((b_val = SvPV(*tmp, PL_na)) == NULL)
    croak("b[1] contains NULL pointer?");


  if ( (tmp = av_fetch(b_arr, 2, 0)) == NULL)
    croak("b[2] is undef");
  if ((b_mask = SvPV(*tmp, PL_na)) == NULL)
    croak("b[2] contains NULL pointer?");

  /* OK, finally we have all of the data! */
  for(i=0;i<20;i++)
  {
    if ((a_val[i] & b_mask[i]) != (b_val[i] & a_mask[i]))
      return 0;
  }
  return 1;
}