Return to Revisions

This brute force approach uses HammingDistance to compare the substrings of the two search strings. To reduce the search time, the longest substrings are compared first. If no match occurs, shorter substrings are used. All matching substrings of the same length are returned.

A helper function, subStrings uses Subsequences to generate all of the substrings of a specified length of the given string.

The main function, longestHammingMatch takes four arguments. the first two are the search strings. The third is minimum length of the substrings to consider. Set the minimum length to 2 or greater to avoid single letter matches. The fourth argument is the number of mismatches that are allowed. Set the 4th argument to 0 for exact match, 1 for 1 letter different, etc.

Clear[subStrings]
subStrings[len_][str_String] := StringJoin @@@ Subsequences[
    Characters@str, {len}] // DeleteDuplicates

Clear[longestHammingMatch]
longestHammingMatch[s1_, s2_, minLength_, maxDiff_] := Reap[
  Block[{tuples, subseq, maxLength, found, 
    start = Min[StringLength /@ {s1, s2}]},
    Do[
      tuples = Select[Tuples[subStrings[len] /@ {s1, s2}],
      StringLength@First[#] == StringLength@Last[#] &];
 
      subseq = 
      Table[{If[maxDiff >= HammingDistance @@ t, len, 0], t}, {t, 
        tuples}];
 
      found = Select[subseq, First[#] == len &];
      If[Length@found > 0, Sow[Last /@ found]; Break[]],
 
      {len, start, minLength, -1}]]][[2]]

Example usage

Define the search strings --

{s1, s2} = {"AAABBBBCCCCC", "CCCBBBAAABABA"}

Search for the longest exact match using at substrings with at least 3 letters:

longestHammingMatch[s1, s2, 3, 0]   (*  {{{{"AAAB", "AAAB"}}}}   *)

Search for the longest match using at substrings with at least 3 letters and allowing at most 1 mismatch. This is the example in the OP:

longestHammingMatch[s1, s2, 3, 1]   (*  {{{{"AAABBB", "AAABAB"}}}}  *)

Search for the longest match using at substrings with at least 3 letters and allowing at most 2 mismatches:

longestHammingMatch[s1, s2, 3, 2]   (*  {{{{"AAABBBB", "AAABABA"}}}}  *)

Try to find a match with at least 8 letters and up to 3 mismatched characters:

longestHammingMatch[s1, s2, 8, 3]   (*  {}  *)

The last example search failed to find a match that met criteria, so an empty list of matches was returned.