An algorithm to find substrings that are nearly anagrams of a search string.

fuzzy_anagram_search.js

function nearly_anagrams(str1,str2,max_diff){
      //max_diff is the maximum difference in the number of characters.
      //Example usage:
      //console.log(JSON.stringify(nearly_anagrams("hello","aahelloaaahello",1)));
      
    	let str1_chars = {}; //number of chars in str1
      let char_diff = {}; //number of chars in the current substring
      let sum_of_diff = 0; //sum of differences between number of each character
      let results = [];
    	for(const i of str1){
      	if(!(i in str1_chars)) str1_chars[i] = 0;
        str1_chars[i] += 1;
      }
      for(const i in str1_chars){
      	char_diff[i] = str1_chars[i];
      }
      for(const i of str2.substring(0,str1.length)){
      	if(i in str1_chars)
        char_diff[i] -= 1;
      }
      for(const i in char_diff){
      	sum_of_diff += Math.abs(char_diff[i]);
      }
      //alert(JSON.stringify("Difference: " + sum_of_diff));
      
      //calculate the rolling sums
      for(var i = 0; i < str2.length-str1.length; i++){
      	if((str2[i] in str1_chars)){
        	//when the first character is in the search string
        	sum_of_diff -= Math.abs(char_diff[str2[i]]);
        	char_diff[str2[i]] += 1;
          sum_of_diff += Math.abs(char_diff[str2[i]]);
        }
        let i1 = i+str1.length;
        if((str2[i1] in str1_chars)){
        	//when the last character is in the search string
        	//alert(char_diff[str2[i1]]);
        	sum_of_diff -= Math.abs(char_diff[str2[i1]]);
        	char_diff[str2[i1]] -= 1;
          sum_of_diff += Math.abs(char_diff[str2[i1]]);
        }
      if(sum_of_diff <= max_diff){
      	results.push(str2.substring(i+1,i+str1.length+1));
      }
      }
      return results;
    }