Алгоритм Ландау-Вишкина (k несовпадений)

Материал из Викиконспекты
Перейти к: навигация, поиск

Постановка задачи

Дано число [math]k \gt 0[/math] текст [math]y[1...n][/math] и образец [math]x[1...m][/math], [math]m \lt n[/math]. Требуется найти все подстроки текста длины [math]m[/math], с не более чем [math]k[/math] несовпадающими символами.

Алгоритм

В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.

При анализе текста используется двумерный массив [math]tm[0...n-m][1...k+1][/math], содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его [math]i[/math]-й строке содержатся позиции в [math]x[/math] первых [math]k+1[/math] несовпадений между строками [math]x[1...m][/math] и [math]y[i+1...i+m][/math]. Таким образом, если [math]tm[i][v] = s[/math], то [math]y[i+s] \neq x[s][/math], и это [math]v[/math]-е несовпадение между [math]x[1...m][/math] и [math]y[i+1...i+m][/math], считая слева направо. Если число [math]d[/math] несовпадений [math]x[1...m][/math] с подстрокой [math]y[i+1...i+m][/math] меньше [math]k+1[/math], то, начиная с [math]d+1[/math], элементы [math]i[/math]-й строки равны значению по умолчанию [math]m+1[/math].

Заметим, если [math]tm[i][k+1] = m+1[/math], то подстрока [math]y[i+1...i+m][/math] отличается от образца [math]x[/math] не более, чем на [math]k[/math] символов, и, таким образом, является решением задачи.

Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации [math]i[/math] с образцом сравнивается подстрока [math]y[i+1...i+m][/math]. [math]j[/math] - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть [math]j[/math] является максимальным из чисел [math]r+tm[r, k + 1][/math], где [math]0 \leqslant r \lt i[/math]. Если [math]i \lt j[/math], в [math]b[/math] присваивается результат работы [math]merge[/math], которая находит количество несовпадений между [math]x[1... j-i][/math] и [math]y[i+1...j][/math]. Если [math]b[/math] не превышает [math]k[/math], вызывается процедура [math]extend[/math], которая сравнивает подстроки [math]y[j + 1...i + m][/math] и [math]x[j - i + 1...m][/math]. Переменная [math]r[/math] будет рассмотренна ниже.

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)

Подстроки, которые сравниваются в процедуре extend

Рассмотрим процедуру [math]extend[/math] подробнее. Она сравнивает подстроки [math]y[j + 1...i + m][/math] и [math]x[j - i + 1...m][/math], в случае несовпадения [math]b[/math] увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено [math]k + 1[/math] несовпадений (учитывая несовпадения, которые были найдены раньше на [math]i[/math]-ой итерации), либо не будет достигнуто [math]y[i+m][/math] с не больше чем [math]k[/math] несовпадениями, то есть найдено вхождение образца, начинающееся с [math]y[i+1][/math].

extend(i, j, b)
while (b < k + 1) and (j - i < m) 
  j++
  if y[j] != x[j-1]
    b++
    tm[i][b] = j - i

Пример

Пусть [math]x = "tram"[/math], [math]y = "thetrippedtrap"[/math], [math]k = 2[/math].

tm 1 2 3 x[1..m] y[i+1..i+m]
0 2 3 4 tram thet
1 1 2 3 tram hetr
2 1 2 3 tram etri
3 3 4 5 tram trip
4 1 2 3 tram ripp
5 1 2 3 tram ippe
6 1 2 3 tram pped
7 1 2 3 tram pedt
8 1 2 3 tram edtr
9 1 2 3 tram dtra
10 4 5 5 tram trap
tm 1 2 3 4 5 x[1..m-i] x[i+1..m]
1 1 2 3 5 5 tra ram
2 1 2 5 5 5 tr am
3 1 5 5 5 5 t m