Алгоритм Ландау-Вишкина (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] несовпадающими символами.

Основная идея

При анализе текста используется двумерный массив [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][v] = \begin{cases} s, //todo\\ m+1, //todo \end{cases}[/math]

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

Пример

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

Файл:Algorithm-landau-vishkin-tm.png

dfdf, dfdf.