I don't know about "best way" - I suspect String::Approx is about as good as we have right now. Here's an approach that may give some food for thought though:

  # assuming $left sequence is the longer one
  my $len = length($right);
  my @matches = map {
    (substr($left, $_, $len) ^ $right) =~ tr/\0/\0/
  } 0 .. length($left) - $len;
[download]

This takes advantage of the fact that the exclusive-or of two characters is zero iff the two characters are the same, to give a list of the number of matching characters when you line $right up against each position of $left.

You may also want to take a look at the recent thread non-exact regexp matches, particularly the references to Text::Levenshtein and List::Compare - the author there appears to be trying to solve a harder problem, so you may find what you want falling out trivially from one of the proposed solutions there.

Hugo