Печать самой длинной общей подпоследовательности

01.01.2020Строки

Учитывая две последовательности, выведите самую длинную подпоследовательность, присутствующую в обеих.

Примеры:
LCS для входных последовательностей «ABCDGH» и «AEDFHR» — это «ADH» длины 3.
LCS для входных последовательностей «AGGTAB» и «GXTXAYB» — это «GTAB» длины 4.

Мы обсуждали проблему Longest Common Subsequence (LCS) в предыдущем посте . Обсуждаемая функция была в основном для определения длины LCS. Чтобы найти длину LCS, была построена двухмерная таблица L [] []. В этом посте обсуждается функция построения и печати LCS.

Ниже приведен подробный алгоритм печати LCS. Он использует ту же 2D таблицу L [] [].

1) Постройте L [m + 1] [n + 1], используя шаги, описанные в предыдущем посте .

2) Значение L [m] [n] содержит длину LCS. Создайте массив символов lcs [] длиной, равной длине lcs плюс 1 (один дополнительный для сохранения / 0).

2) Перейдите 2D массив, начиная с L [m] [n]. Делайте следующее для каждой ячейки L [i] [j]
… .. a) Если символы (в X и Y), соответствующие L [i] [j], одинаковы (или X [i-1] == Y [j-1]), то включите этот символ как часть LCS ,
… .. b) В противном случае сравните значения L [i-1] [j] и L [i] [j-1] и перейдите в направлении большего значения.

В следующей таблице (взято из Wiki ) показаны шаги (выделены), за которыми следует приведенный выше алгоритм.

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	A	W	X	U
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Ниже приводится реализация вышеуказанного подхода.

C / C ++

/ * Динамическое программирование реализации задачи LCS * /
#include<iostream>
#include<cstring>
#include<cstdlib>

using namespace std;

/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

void lcs( char *X, char *Y, int m, int n )

{

int L[m+1][n+1];

/ * Следуя шагам, соберите L [m + 1] [n + 1] снизу вверх. Заметка

что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1] * /

for (int i=0; i<=m; i++)

{

for (int j=0; j<=n; j++)

{

if (i == 0 || j == 0)

L[i][j] = 0;

else if (X[i-1] == Y[j-1])

L[i][j] = L[i-1][j-1] + 1;

else

L[i][j] = max(L[i-1][j], L[i][j-1]);

}

// Следующий код используется для печати LCS

int index = L[m][n];

// Создаем массив символов для хранения строки lcs

char lcs[index+1];

lcs[index] = '\0'; // Устанавливаем завершающий символ

// Начинаем с самого правого-самого нижнего угла и

// один за другим сохраняем символы в lcs []

int i = m, j = n;

while (i > 0 && j > 0)

{

// Если текущий символ в X [] и Y совпадает, то

// текущий символ является частью LCS

if (X[i-1] == Y[j-1])

{

lcs[index-1] = X[i-1]; // Поместить текущий символ в результат

i--; j--; index--; // уменьшаем значения i, j и index

}

// Если не одно и то же, то найти большее из двух и

// идти в направлении большего значения

else if (L[i-1][j] > L[i][j-1])

i--;

else

j--;

}

// Распечатать lcs

cout << "LCS of " << X << " and " << Y << " is " << lcs;

}

/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

char X[] = "AGGTAB";

char Y[] = "GXTXAYB";

int m = strlen(X);

int n = strlen(Y);

lcs(X, Y, m, n);

return 0;

}

Джава

// Динамическое программирование реализации задачи LCS в Java

import java.io.*;

class LongestCommonSubsequence

{

// Возвращает длину LCS для X [0..m-1], Y [0..n-1]

static void lcs(String X, String Y, int m, int n)

{

int[][] L = new int[m+1][n+1];

// Следующие шаги строим L [m + 1] [n + 1] снизу вверх. Заметка

// что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1]

for (int i=0; i<=m; i++)

{

for (int j=0; j<=n; j++)

{

if (i == 0 || j == 0)

L[i][j] = 0;

else if (X.charAt(i-1) == Y.charAt(j-1))

L[i][j] = L[i-1][j-1] + 1;

else

L[i][j] = Math.max(L[i-1][j], L[i][j-1]);

}

// Следующий код используется для печати LCS

int index = L[m][n];

int temp = index;

// Создаем массив символов для хранения строки lcs

char[] lcs = new char[index+1];

lcs[index] = ''; // Устанавливаем завершающий символ

// Начинаем с самого правого-самого нижнего угла и

// один за другим сохраняем символы в lcs []

int i = m, j = n;

while (i > 0 && j > 0)

{

// Если текущий символ в X [] и Y совпадает, то

// текущий символ является частью LCS

if (X.charAt(i-1) == Y.charAt(j-1))

{

// Поместить текущий символ в результат

lcs[index-1] = X.charAt(i-1);

// уменьшаем значения i, j и index

i--;

j--;

index--;

}

// Если не одно и то же, то найти большее из двух и

// идти в направлении большего значения

else if (L[i-1][j] > L[i][j-1])

i--;

else

j--;

}

// Распечатать lcs

System.out.print("LCS of "+X+" and "+Y+" is ");

for(int k=0;k<=temp;k++)

System.out.print(lcs[k]);

}

// драйверная программа

public static void main (String[] args)

{

String X = "AGGTAB";

String Y = "GXTXAYB";

int m = X.length();

int n = Y.length();

lcs(X, Y, m, n);

}

// Предоставлено Прамод Кумар

питон

# Динамическое программирование реализации задачи LCS

# Возвращает длину LCS для X [0..m-1], Y [0..n-1]

def lcs(X, Y, m, n):

L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]

# Следуя шагам, постройте L [m + 1] [n + 1] снизу вверх. Заметка

# что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1]

for i in xrange(m+1):

for j in xrange(n+1):

if i == 0 or j == 0:

L[i][j] = 0

elif X[i-1] == Y[j-1]:

L[i][j] = L[i-1][j-1] + 1

else:

L[i][j] = max(L[i-1][j], L[i][j-1])

# Следующий код используется для печати LCS

index = L[m][n]

# Создать массив символов для хранения строки lcs

lcs = [""] * (index+1)

lcs[index] = ""

# Начните с самого правого-самого нижнего угла и

# один за другим сохраняем символы в lcs []

i = m

j = n

while i > 0 and j > 0:

# Если текущий символ в X [] и Y совпадает, то

# текущий символ является частью LCS

if X[i-1] == Y[j-1]:

lcs[index-1] = X[i-1]

i-=1

j-=1

index-=1

# Если не то же самое, то найдите большее из двух и

# идти в направлении большего значения

elif L[i-1][j] > L[i][j-1]:

i-=1

else:

j-=1

print "LCS of " + X + " and " + Y + " is " + "".join(lcs)

# Драйверная программа

X = "AGGTAB"

Y = "GXTXAYB"

m = len(X)

n = len(Y)

lcs(X, Y, m, n)

# Этот код предоставлен BHAVYA JAIN

C #

// Динамическое программирование реализации
// проблемы LCS в C #

using System;

class GFG

{

// Возвращает длину LCS для X [0..m-1], Y [0..n-1]

static void lcs(String X, String Y, int m, int n)

{

int[,] L = new int[m+1, n+1];

// Следующие шаги строим L [m + 1] [n + 1] в

// снизу вверх мода. Обратите внимание, что L [i] [j]

// содержит длину LCS X [0..i-1]

// и Y [0..j-1]

for (int i = 0; i <= m; i++)

{

for (int j = 0; j <= n; j++)

{

if (i == 0 || j == 0)

L[i, j] = 0;

else if (X[i-1] == Y[j-1])

L[i, j] = L[i-1, j-1] + 1;

else

L[i, j] = Math.Max(L[i-1, j], L[i, j-1]);

}

// Следующий код используется для печати LCS

int index = L[m, n];

int temp = index;

// Создать массив символов

// для сохранения строки lcs

char[] lcs = new char[index+1];

// Устанавливаем завершающий символ

lcs[index] = '\0';

// Начинаем с самого правого-самого нижнего угла

// и один за другим сохраняем символы в lcs []

int k = m, l = n;

while (k > 0 && l > 0)

{

// Если текущий символ в X [] и Y

// одинаковы, то текущий символ

// является частью LCS

if (X[k-1] == Y[l-1])

{

// Поместить текущий символ в результат

lcs[index-1] = X[k-1];

// уменьшаем значения i, j и index

k--;

l--;

index--;

}

// Если не одно и то же, то найти большее из двух и

// идти в направлении большего значения

else if (L[k-1, l] > L[k, l-1])

k--;

else

l--;

}

// Распечатать lcs

Console.Write("LCS of " + X + " and " + Y + " is ");

for(int q = 0; q <= temp; q++)

Console.Write(lcs[q]);

}

// Драйвер программы

public static void Main ()

{

String X = "AGGTAB";

String Y = "GXTXAYB";

int m = X.Length;

int n = Y.Length;

lcs(X, Y, m, n);

}

// Этот код предоставлен Sam007

PHP

<?php
// Динамическое программирование реализации задачи LCS

// Возвращает длину LCS для X [0..m-1], Y [0..n-1]

function lcs( $X, $Y, $m, $n )

{

$L = array_fill(0, $m + 1,

array_fill(0, $n + 1, NULL));

/ * Следуя шагам, строим L [m + 1] [n + 1] внизу

до моды. Обратите внимание, что L [i] [j] содержит длину

LCS из X [0..i-1] и Y [0..j-1] * /

for ($i = 0; $i <= $m; $i++)

{

for ($j = 0; $j <= $n; $j++)

{

if ($i == 0 || $j == 0)

$L[$i][$j] = 0;

else if ($X[$i - 1] == $Y[$j - 1])

$L[$i][$j] = $L[$i - 1][$j - 1] + 1;

else

$L[$i][$j] = max($L[$i - 1][$j],

$L[$i][$j - 1]);

}

// Следующий код используется для печати LCS

$index = $L[$m][$n];

$temp = $index;

// Создаем массив символов для хранения строки lcs

$lcs = array_fill(0, $index + 1, NULL);

$lcs[$index] = ''; // Устанавливаем завершающий символ

// Начинаем с самого правого-самого нижнего угла

// и один за другим сохраняем символы в lcs []

$i = $m;

$j = $n;

while ($i > 0 && $j > 0)

{

// Если текущий символ в X [] и Y совпадает,

// тогда текущий символ является частью LCS

if ($X[$i - 1] == $Y[$j - 1])

{

// Поместить текущий символ в результат

$lcs[$index - 1] = $X[$i - 1];

$i--;

$j--;

$index--; // уменьшаем значения i, j и index

}

// Если не одно и то же, то найти большее из двух

// и идти в направлении большего значения

else if ($L[$i - 1][$j] > $L[$i][$j - 1])

$i--;

else

$j--;

}

// Распечатать lcs

echo "LCS of " . $X . " and " . $Y . " is ";

for($k = 0; $k < $temp; $k++)

echo $lcs[$k];

}

// Код драйвера

$X = "AGGTAB";

$Y = "GXTXAYB";

$m = strlen($X);

$n = strlen($Y);

lcs($X, $Y, $m, $n);

// Этот код поддерживается ita_c
?>

Выход:

LCS of AGGTAB and GXTXAYB is GTAB

Ссылки:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Печать самой длинной общей подпоследовательности

0.00 (0%) 0 votes