The ApproximateSearch(pattern, text, k) command locates the first occurrence of a substring of the string text that is close to the string pattern in terms of its Levenshtein distance from pattern. Specifically, it locates the first such substring whose Levenshtein distance from pattern is less than or equal to k.

The ApproximateSearchAll(pattern, text, k) command locates all occurrences of substrings of the string text that are within Levenshtein distance k of the string pattern. An expression sequence of offsets marking the ends of matches is returned.

Note that for $k=0$, approximate searching degenerates into exact searching, for which StringTools[Search] and StringTools[SearchAll] provide faster algorithms.

If $\mathrm{length}\left(\mathrm{pattern}\right)\le k$, then every possible substring of text with length equal to the length of pattern matches pattern.

For a related concept that uses the Hamming metric instead of the edit distance, see StringTools[HammingSearch].

All of the StringTools package commands treat strings as (null-terminated) sequences of $8$-bit (ASCII) characters.  Thus, there is no support for multibyte character encodings, such as unicode encodings.

$\mathrm{with}\left(\mathrm{StringTools}\right)\:$

$\mathrm{ApproximateSearch}\left(''foo''\,''defoe''\,0\right)$

$0$

$\mathrm{ApproximateSearch}\left(''foo''\,''defoe''\,1\right)$

$4$

$\mathrm{ApproximateSearch}\left(''foo''\,''defoe''\,2\right)$

$3$

$\mathrm{ApproximateSearch}\left(''foo''\,''defoe''\,3\right)$

$1$

$\mathrm{ApproximateSearch}\left(''foo''\,''defoe''\,4\right)$

$1$

$\mathrm{ApproximateSearch}\left(''gataa''\,''cagataagagaa''\,2\right)$

$5$

$\mathrm{ApproximateSearchAll}\left(''gataa''\,''cagataagagaa''\,2\right)$

$5,6,7,8,9,11,12$