Учитывая строку и шаблон, которые нужно сопоставить, насколько эффективно можно найти совпадения, имеющие ноль или одно несоответствие.
e.g)
S = abbbaaabbbabab
P = abab
Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)
Я пытался изменить алгоритм KMP, но я не уверен в подходе.
Пожалуйста, дайте мне идею, чтобы продолжить с проблемой.
Спасибо.
Хорошо, я нашел это! Я нашел лучший алгоритм!
Это может показаться немного смелым, но пока алгоритм, который я собираюсь предложить, имеет время выполнения O(m + n) и потребление памяти O(m + n), а сами входные данные имеют те же свойства, алгоритм можно оптимизировать только в константе.
Я собираюсь использовать смесь алгоритмов KMP и Rabin Karp для мое решение. Рабин Карп использует скользящие хэши для сравнения подстрок исходных строк. Это требует линейного во времени предварительного вычисления, которое использует линейную дополнительную память, но с этого момента сравнение между подстроками двух строк является постоянным O(1) (это амортизируется, если вы правильно обрабатываете коллизии).
Мое решение не найдет все вхождения в первой строке, которые соответствуют второй строке с не более чем 1 отличием. Однако алгоритм можно модифицировать так, чтобы для каждого начального индекса в первой строке, если есть такое совпадение, был найден хотя бы один из них (это предоставляется читателю).
Пусть m будет длиной второй строки, а n - длиной первой строки. Я собираюсь разделить задачу на две части: если я стремлюсь найти соответствие не более чем с одним отличием, я хочу найти подстроки первой строки: PREF будет подстрокой перед единственной разницей, а SUFF — подстрокой. подстрока после разницы. Я хочу len(PREF) + len(SUFF) + 1 = m, где PREF или SUFF будут искусственно сокращены при необходимости (когда строки совпадают без разницы).
Я собираюсь основывать свое решение на одном очень важном наблюдении: предположим, что существует подстрока первой строки, начинающаяся с индекса i и имеющая длину m, которая соответствует второй строке не более чем с одним отличием. Тогда, если мы возьмем PREF как можно дольше, решение для SUFF все равно будет. Это очевидно: я просто довожу разницу до конца.
А теперь следует сам алгоритм. Начните с обычного KMP. Каждый раз, когда расширение префикса терпит неудачу и необходимо перейти по неудачным ссылкам, сначала проверьте, будет ли оставшийся суффикс соответствовать оставшейся части второй строки, если вы пропустите следующую букву. Если да, то найдено искомое совпадение, отличающееся не более чем одним символом. Если нет - продолжаем обычный КМП, делая проверку Рабина Карпа каждый раз, когда нужно перейти по неудачной ссылке.
Поясню далее проверку Рабина Карпа на примере. Предположим, мы находимся на определенном шаге KMP и обнаружили, что first.substring[i, i + k - 1] соответствует первым k буквам второй строки. Предположим также, что буква first[i + k] отличается от second[k]. Затем вы проверяете, соответствует ли first.substring[i + k + 1, i + m - 1] точно second.substring[k + 1, m - 1], используя Рабина Карпа. Это как раз тот случай, когда вы максимально расширили индекс формы начального префикса i и теперь пытаетесь найти совпадение не более чем с одним отличием.
Рабин Карп будет использоваться только при переходе по неудачной ссылке, которая перемещает начальный индекс префикса как минимум на единицу, что означает, что используется не более O(n) вызовов Рабина Карпа, каждый со сложностью O(1) для общей линейной сложности.
Это известно как проблема приблизительного сопоставления строк. В вашем конкретном случае вам нужно максимальное расстояние редактирования, равное 1.
алгоритм bitap — довольно быстрый способ решения этой проблемы.
Чтобы найти все подсовпадения, включая одно несоответствие, вам нужны 2 z-функции (одна для исходного P, а другая для обратного P). После этого создайте массив самых длинных префиксных совпадений для исходной и перевернутой строки S. Позже вам нужно перевернуть второй массив. А в итоге все просто: пробегаемся по первому массиву и проверяем, равна ли длина самого длинного префикса длине P. Если да, то совпадение без ошибок. Если он короче, то проверьте второй массив в позиции (i + length(P) - 1). Если сумма двух значений равна length(P) - 1, то это подсовпадение с одной ошибкой.
Сложность O (len (P) + len (S))
Всесторонний обзор различных алгоритмов и их сравнения друг с другом представлен Гонсало Наварро в его Экскурсия по приблизительному сопоставлению строк. На страницах 80, 81 и 82 показаны результаты сложности, включая наихудшие и средние случаи, а также требования к пространству для различных алгоритмов.
(В используемых там обозначениях n относится к длине текста, который вы ищете, m к длине шаблона, к размеру алфавита, а k к максимальному расстоянию редактирования, которое в вашем случае равно 1 .)
