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