Кто-нибудь знает или имеет какое-либо представление о том, можно ли изменить алгоритм KMP для поиска по подстроке, чтобы найти не точные совпадения, а приблизительные?
Посмотрите на алгоритм Bitap .