stringFuzzilyContains.md

This naive algorithm compares two strings, needle and haystack. It returns true if haystack "fuzzily" contains needle, which is when (almost) every character in needle is found in (almost) the same order, but not necessarily contiguously, in haystack. Up to allowed_errors characters in needle are allowed to not be found in haystack. Characters may also be swapped.

The following is a python implementation:

def stringFuzzilyContains(needle, haystack):
    # allow this many characters to not be found
    allowed_errors = 0
    
    # the last index where a character was found;
    # will begin search for next character only up to 1 position before this.
    last_found_index = 0
    
    # prevent reverse-searching by only stepping back once at a time
    did_step_back = False
    
    for c1 in needle:
        found_c1 = False
        for index in range(last_found_index - 1, len(haystack)):
            if index >= 0 and c1 == haystack[index] and not did_step_back:
                found_c1 = True
                did_step_back = index == last_found_index - 1
                last_found_index = index
                break
        if not found_c1:
            if allowed_errors > 0:
                allowed_errors -= 1
            else:
                return False
    return True