use strict;
use warnings;

my $test = "abcdefghijklmnopqrstuvwxy";
my @test = split //,$test;
my $dict = "qqqabcdefghijklmnopqrstuvwxyqqq";
my @dict = split //,$dict;

my $dict_pos = 0;  # where in the dictionary word
my $at_pos = 0;    # where in the test word
my $fuzzies = 2;   # unused fuzzies remaining
my $testlen = length($test);
my $len = length($dict) - $testlen - 1;

# This loop illustrates the states a finite state machine would
# require.  The states would be numbered 3*$at_pos + $fuzzies,
# that is, 75 states in this case.
while (1) {
   if ($fuzzies > 0) {
      if ($dict[$dict_pos + $at_pos] ne $test[$at_pos]) {
         --$fuzzies;
      }
      ++$at_pos;
      if ($at_pos >= $testlen) {
         print "Found at $dict_pos with $fuzzies remaining\n";
         last;
      }
   } else {
      # Out of fuzzies.  Rest of match must be exact, or start over
      # in the next position.
      my $s1 = substr($dict, $dict_pos + $at_pos, $testlen - $at_pos);
      my $s2 = substr($test, $at_pos);
      if ($s1 ne $s2) {
         last if (++$dict_pos > $len);
         $fuzzies = 2;
         $at_pos = 0;
      } else {
         print "Found at $dict_pos with $fuzzies remaining\n";
         last;
      }
   }
}
[download]