AppleFritter has probably provided you with what you need, with quite a number of details. Just a couple of additional clues.

One thing you might do is to google for the Baeza-Yates k-mismatches algorithm, the Wu-Manber k-differences algorithm and the longest common subsequence (LCS) algorithms.

Some additional modules of possible interest: Jarkko Hietaniemi's String::Approx and Mark-Jason Dominus' Algorithm::Diff.