297
правок
Изменения
→Основная идея
==Основная идея==
При анализе текста используется двумерный массив <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] \neq 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>. То есть
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации <tex>i</tex> с образцом сравнивается подстрока <tex>y[i+1...i+m]</tex>. <tex>j</tex> - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть <tex>j</tex> является максимальным из чисел <tex>r+tm[r, k + 1]</tex>, где <tex>0 <= r < i</tex>//todo. Если <tex>i < j</tex>, в <tex>b</tex> присваивается результат работы <tex>merge</tex>, которая находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>extend</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>.
Переменная <tex>r</tex> будет рассмотренна ниже.
{| border="0"
|align="left" colspan="4"|
<font size=3>
tm[0...n-m][1...k+1] = m+1 // инициализация
r = 0
j = 0
for i = 0 to n - m
b = 0
if i < j
b = merge(i, r, j)
if b < k + 1
r = i
extend(i, j, b)
</font>
|}
и в случае несовпадения <tex>b</tex> увеличивается и таблица текстовых несовпадений обновляется. Если найдено <tex>k+1</tex> несовпадений, обработка заканчивается, иначе найдено вхождение образца в подстроке <tex>y[i+1...i+m]</tex>.
==Пример==
