Изменения
Новая страница: «==Постановка задачи== Дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>....»
==Постановка задачи==
Дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами.
==Основная идея==
При анализе текста используется двумерный массив <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>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами.
==Основная идея==
При анализе текста используется двумерный массив <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>.
