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