Изменения

|definition = По заданному слову <tex>x[0..\ldots m-1]</tex> найти в тексте или словаре <tex>y[0..\ldots n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.

Алгоритм k различий Ландау-Вишкина основан на подходе, близком методу [[Динамическое_программирование|динамического программирования ]] для вычисления расстояния между строками, который предложил Укконен<ref>[http://link.springer.com/chapter/10.1007%2F3-540-12689-9_129#page-1 Esko Ukkonen {{---}} On approximate string matching]</ref>. Перед тем, как перейти к этому алгоритму, рассмотрим метод динамического программирования и его адаптацию в стиле Укконена.

В приведенном выше алгоритме перед циклом <tex>\mathrm{while}</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(0, r - 1)</tex> сопоставляется с точностью до <tex>k</tex> различий с некоторой подстрокой текста, заканчивающейся <tex>y_{r+p}</tex>. Тогда функция цикла <tex>\mathrm{while}</tex> находит максимальное значение для которого <tex>x(r+1, r+h) = y(r+p+1, r+p+h)</tex>. Обозначим это значение как <tex>h</tex>. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+1, m)\$</tex> и <tex>y(r+p+1,n){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки. Символ <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, так и <tex>x</tex>. Обозначим <tex>lca(r,p)</tex> как [[Сведение_задачи_LCA_к_задаче_RMQ#lca_suf_tree|самый низкий общий предок]] в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.