297
правок
Изменения
Нет описания правки
[[Файл:algLandauVishkin4.png|thumb|250px|right| В таблицу pm по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть <tex>pm[i][1] = a</tex>, <tex>pm[i][2] = b</tex>, <tex>pm[i][3] = c</tex> и т д.]]
Также в алгоритме используется двумерный массив несовпадений образца <tex>pm[1...m-1][1...2k+1]</tex>, генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично <tex>tm</tex>, то есть ест{{---}}ь в <tex>i</tex>-ой строке содержатся позиции внутри <tex>x</tex> первых <tex>2k+1</tex> несовпадений между подстроками <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex>. Таким образом, если <tex>pm[i][v] = s</tex>, то <tex>x[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex> слева направо. Если число <tex>d</tex> несовпадений между этими строками меньше <tex>2k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны <tex>m+1</tex>, значению по умолчанию. Построение <tex>tm</tex> будет подробнее рассмотрено позднее.
Таким образом, для <tex>merge</tex> интерес представляет строка <tex>i - r</tex> таблицы несовпадений образца, причем используются значения <tex>pm[i-r][1...t]</tex>, где <tex>t</tex> {{---}} самое правое несовпадение в <tex>pm[i-r][1...2k+1]</tex>, такое, что <tex>pm[i-r][t] < j-i+1</tex>, так как требуются только несовпадения в подстроке <tex>x[1...j-i]</tex>.
| '''3''' || 1 || 5 || 5 || 5 || 5 || t || m
|}
==См. также==
* [http://algolist.manual.ru/search/fsearch/k_razl.php Алгоритм Ландау-Вишкина - k различий]
==Источники информации==
* [http://algolist.manual.ru/search/fsearch/k_nesovp.php Алгоритм Ландау-Вишкина - k несовпадений]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
