http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=5.18.154.84&*Викиконспекты - Вклад участника [ru]2026-05-15T10:26:41ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B0%D0%BD%D0%B4%D0%B0%D1%83-%D0%92%D0%B8%D1%88%D0%BA%D0%B8%D0%BD%D0%B0_(k_%D0%BD%D0%B5%D1%81%D0%BE%D0%B2%D0%BF%D0%B0%D0%B4%D0%B5%D0%BD%D0%B8%D0%B9)&diff=39226Алгоритм Ландау-Вишкина (k несовпадений)2014-06-14T19:18:40Z<p>5.18.154.84: </p>
<hr />
<div>==Постановка задачи==<br />
Дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами.<br />
<br />
==Основная идея==<br />
При анализе текста используется двумерный массив <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>. Таким образом, если <tex>tm[i][v] = s</tex>, то <tex>y[i+s]</tex> =/= <tex>x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>, считая слева направо. Если число <tex>d</tex> несовпадений <tex>x[1...m]</tex> с подстрокой <tex>y[i+1...i+m]</tex> меньше <tex>k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны значению по умолчанию <tex>m+1</tex>.</div>5.18.154.84http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B0%D0%BD%D0%B4%D0%B0%D1%83-%D0%92%D0%B8%D1%88%D0%BA%D0%B8%D0%BD%D0%B0_(k_%D0%BD%D0%B5%D1%81%D0%BE%D0%B2%D0%BF%D0%B0%D0%B4%D0%B5%D0%BD%D0%B8%D0%B9)&diff=39225Алгоритм Ландау-Вишкина (k несовпадений)2014-06-14T19:05:48Z<p>5.18.154.84: Новая страница: «==Постановка задачи== Дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>....»</p>
<hr />
<div>==Постановка задачи==<br />
Дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами.<br />
<br />
==Основная идея==<br />
При анализе текста используется двумерный массив <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>.</div>5.18.154.84