Контрольная работа по "Информатике"

Z=⟨D,E,F,G,H⟩

Подсчитаем V=LCS(X,Y)=⟨A,B,C⟩

LCS(Z,V)=∅

Это неверно, так как LCS(X,Y,Z)=⟨D,E⟩

Теорема:

Пусть имеются последовательности X=⟨x1,x2,…,xm⟩, Y=⟨y1,y2,…,yn⟩ и Z=⟨z1,z2,…,zk⟩, а V=⟨v1,v2,…,vh⟩ — их LCS.

Если zk=xm=yn, то zk=xm=yn=vh и Vh−1 — LCS(Xm−1,Yn−1,Zk−1)

Если zk≠xm≠yn, то из zk≠vh следует, что V — LCS(Xm,Yn,Zk−1)

Если zk≠xm≠yn, то из yn≠vh следует, что V — LCS(Xm,Yn−1,Zk)

Если zk≠xm≠yn, то из xm≠vh следует, что V — LCS(Xm−1,Yn,Zk)

Доказательство:

▹

Доказательство аналогично доказательству для двух последовательностей.

◃

Решение

Обозначим как lcs[i][j][l] наибольшую общую подпоследовательность префиксов данных последовательностей, заканчивающихся в элементах с номерами i, j и l соответственно. Получается следующее рекуррентное соотношение:

lcs[i][j][l]=⎧⎩⎨0,lcs[i−1][j−1][l−1]+1,max(lcs[i][j−1][l], lcs[i−1][j][l], lcs[i][j][l−1]),i=0 or j=0 or l=0x[i]=y[j]=z[l]x[i]≠y[j]≠z[l]

Очевидно, что сложность алгоритма составит O(mnk), где m, n и k — длины последовательностей.

Аналогичным образом задача решается для k строк. Заполняется k-мерная динамика.

Алгоритм Хиршберга

Задача:

Пусть имеются последовательности X=⟨x1,x2,…,xm⟩ и Y=⟨y1,y2,…,yn⟩. Необходимо найти LCS(X,Y) за время O(nm) и O(n+m) памяти.

Алгоритм

Не теряя общности, будем считать, что m⩾n. Тогда разобьем последовательность X на две равные части x1[0…m2] и x2[m2+1…m]. Найдем LCS для x1 и всех префиксов последовательности Y, аналогично — для развернутых последовательностей x2 и Y. Стоит отметить, что для нахождения LCS на всех префиксах достаточно одного квадратичного прохода, так как i-ый элемент последней строки результирующей матрицы есть не что иное, как LCS первой последовательности и префикса второй длины i. Затем выберем такой индекс j, что |LCS(x1,y[0…j])+LCS(reverse(x2),reverse(y[j+1…n]))|=max. Запустим алгоритм рекурсивно для пар (x1,y[0…j]) и (x2,y[j+1…n]). Будем продолжать до тех пор, пока в X не останется ровно 1 элемент, тогда достаточно проверить, входит ли он текущую часть Y, если входит, то добавим этот символ в ответ, если нет — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.

Псевдокод

В данном примере x,y — последовательности, ans — вектор ответа. LCS — функция, возвращающая последнюю строку матрицы lcs, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы lcs в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.

void hirschberg(x: vector, y: vector):

if y.size() <= 0

return

if x.size() == 1

if y.contains(x[0])

ans.push(x[0]) // сохранение очередного элемента lcs