Нахождение нечеткого совпадения с помощью алгоритма bitap

Question

В последнее время я просмотрел несколько реализаций алгоритма bitap, но все они находят начальную точку нечеткого совпадения. Что мне нужно, это найти совпадение. Вот пример:

Скажем, у нас есть следующий текст: abcdefg

и рисунок: bzde

и мы хотим найти все вхождения шаблона в тексте с ошибкой не более 1 (расстояние редактирования считается оконченным).

Так что мне нужно, чтобы алгоритм возвращал: bcde.

Есть ли простой (или не простой =) способ сделать это? Оригинальная статья об этом алгоритме не дает ответа на вопрос.

Спасибо за вашу помощь.

Answer 1

Для простого начала вы можете подойти к нему с помощью серии регулярных выражений, где в каждом выражении вы заменяете 1 символ подстановочным знаком .. Объединение этих выражений в одно с помощью конструкции ( | ) для создания одного большого регулярного выражения.

Другим способом было бы отсканировать строку, сохраняя количество ошибок и увеличивая смещение, с которым вы подходите, когда встречается слишком много ошибок.