Алгоритм Ландау-Вишкина (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

Синие подстроки сравниваются в процедуре 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

merge

Синие подстроки сравниваются в процедуре merge. Красным отмечены несовпадения.

Рассмотрим процедуру [math]merge[/math] подробнее. Она находит количество несовпадений между [math]x[1... j-i][/math] и [math]y[i+1...j][/math] и устанавливает b равным найденному числу, при этом используется полученая ранее информация. Введем [math]r[/math] - это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и [math]y[r+1][/math]. [math]r+tm[r][k+1][/math] содержит текущий номер самой правой из проверенных на настоящий момент позиций текста. Поэтому при обработки построки начинающейся с [math]y[i+1][/math], можно учитывать информацию в [math]r[/math]-ой строке [math]tm[/math], которая содержит информацию о сопоставлении образца с [math]y[i][/math]. Подходящими значениями из таблицы несовпадений являются, таким образом, [math]tm[r][q ... k+1][/math], где [math]q[/math] – это наименьшее из целых чисел, для которых [math]r+tm[r][q] \gt i[/math]. Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, выравниваемому с [math]y[r+1][/math], в то время как текущая позиция образца выровнена с [math]y[i+1][/math] – разница в [math]i - r[/math] мест.

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

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

Таким образом, для [math]merge[/math] интерес представляет строка [math]i - r[/math] таблицы несовпадений, причем используются значения [math]pm[i-r][1...t][/math], где [math]t[/math] – самое правое несовпадение в [math]pm[i-r][1...2k+1][/math], такое, что [math]pm[i-r][t] \lt j-i+1[/math], так как требуются только несовпадения в подстроке [math]x[1...j-i][/math].

Чтобы использовать упомянутую информацию в процедуре [math]merge[/math], рассмотрим в тексте позицию [math]p[/math], находящуюся в диапазоне, [math]i+1 \lt p \lt j[/math]. Рассмотрим следующие условия для позиции [math]p[/math]:

Условие A: когда символы [math]x[1][/math] и [math]y[r+1][/math] совмещены, позиция [math]p[/math] в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть [math]y[p] \neq x[p-r][/math], и это несовпадение номер [math]v[/math], где [math]q \lt v \lt k+1[/math], то есть [math]p - r = tm[r][v][/math].

Условие B: для двух копий образца, со сдвигом относительно друг друга [math]i - r[/math], совмещенных с текстом так, что их начальные символы лежат, соответственно, над [math]y[r+1][/math] и [math]y[i+1][/math], позиция [math]p[/math] соответствует несовпадению между двумя шаблонами, то есть [math]x[p-r] \neq x[p-i]\lt tex\gt . Это \lt tex\gt u[/math]-е несовпадение при этом сдвиге, где [math]1 \lt u \lt t[/math], то есть [math]p-i[/math] = [math]pm[i-r][u][/math].

Пример

Пусть [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