Самая длинная общая подпоследовательность

ProgramBox

Самая длинная общая подпоследовательность | DP-4

Post author:admin
Запись опубликована:18 декабря, 2021
Post category:JavaScript язык программирования / C# язык программирования / PHP язык программирования / Python язык программирования

Давайте обсудим проблему с самой длинной общей подпоследовательностью (LCS) в качестве еще одного примера проблемы, которую можно решить с помощью динамического программирования.

Постановка задачи LCS: Учитывая две последовательности, найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность-это последовательность, которая отображается в том же относительном порядке, но необязательно непрерывная. Например, “abc”, “abg”, “bdf”, “aeg”, » acefg” и т. Д. Являются подпоследовательностями “abcdefg”.

Чтобы выяснить сложность подхода с использованием грубой силы, нам нужно сначала узнать количество возможных различных подпоследовательностей строки длиной n, т. е. Найти количество подпоследовательностей длиной от 1,2,..n-1. Напомним из теории перестановок и комбинаций, что число комбинаций с 1 элементом равно ⁿC₁. Количество комбинаций с 2 элементами равно ⁿC₂ и так далее, и так далее. Мы знаем, что ⁿC₀ + ⁿC₁ + ⁿC₂ + … ⁿC_n = 2ⁿ. Таким образом, строка длины n имеет 2ⁿ-1 различные возможные подпоследовательности, так как мы не рассматриваем подпоследовательность длиной 0. Это означает, что временная сложность подхода с использованием грубой силы будет O(n * 2ⁿ). Обратите внимание, что для проверки того, является ли подпоследовательность общей для обеих строк, требуется O(n) времени. На этот раз сложность может быть улучшена с помощью динамического программирования.

Это классическая задача в области информатики, основа diff (программа сравнения файлов, которая выводит различия между двумя файлами) и имеет приложения в биоинформатике.

Примеры:

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

Наивное решение этой проблемы состоит в том, чтобы сгенерировать все подпоследовательности обеих заданных последовательностей и найти самую длинную совпадающую подпоследовательность. Это решение является экспоненциальным с точки зрения сложности во времени. Давайте посмотрим, как эта проблема обладает обоими важными свойствами задачи динамического программирования (DP).

1) Оптимальная подструктура:

Пусть входные последовательности будут X[0..m-1] и Y[0..n-1] длин m и n соответственно. И пусть L(X[0..m-1], Y[0..n-1]) — длина LCS двух последовательностей X и Y. Ниже приводится рекурсивное определение L(X[0..m-1], Y[0..n-1]).

Если последние символы обеих последовательностей совпадают (или Х[М-1] == м[п-1]), то
L(Х[0..М-1] и y[0..П-1]) = 1 + л(х[0..м-2] и y[0..п-2])

Если последние символы в обеих последовательностях не совпадают (или Х[М-1] != У[п-1]), то
L(Х[0..М-1] и y[0..П-1]) = Макс ( Л(Х[0..м-2] и y[0..П-1]), L(Х[0..М-1] и y[0..п-2]) )

Примеры:

1) Рассмотрим входные строки “AGGTAB” и “GXTXAYB”. Последние символы совпадают для строк. Таким образом, длина LCS может быть записана как:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

2) Рассмотрим входные строки “ABCDGH” и “AEDFHR. Последние символы не совпадают для строк. Так длина LCS можно записать так:
л(“ABCDGH”, “AEDFHR”) = Макс ( л(“ABCDG”, “AEDFHР”), Л(“ABCDGч”, “AEDFH”) )
так что LCS проблема имеет оптимальную подструктуру собственность как основная проблема может быть решена с помощью решения для подзадач.

2) Перекрывающиеся подзадачи:

Ниже приведена простая рекурсивная реализация проблемы LCS. Реализация просто следует рекурсивной структуре, упомянутой выше.

/* A Naive recursive implementation of LCS problem */
#include <bits/stdc++.h>
using namespace std;

int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
	if (m == 0 || n == 0)
		return 0;
	if (X[m-1] == Y[n-1])
		return 1 + lcs(X, Y, m-1, n-1);
	else
		return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
	return (a > b)? a : b;
}

/* Driver code */
int main()
{
	char X[] = "AGGTAB";
	char Y[] = "GXTXAYB";
	
	int m = strlen(X);
	int n = strlen(Y);
	
	cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
	
	return 0;
}

// This code is contributed by rathbhupendra

/* A Naive recursive implementation of LCS problem */
#include<bits/stdc++.h>

int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
	return 0;
if (X[m-1] == Y[n-1])
	return 1 + lcs(X, Y, m-1, n-1);
else
	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
	return (a > b)? a : b;
}

/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";

int m = strlen(X);
int n = strlen(Y);

printf("Length of LCS is %d", lcs( X, Y, m, n ) );

return 0;
}

/* A Naive recursive implementation of LCS problem in java*/
public class LongestCommonSubsequence
{

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char[] X, char[] Y, int m, int n )
{
	if (m == 0 || n == 0)
	return 0;
	if (X[m-1] == Y[n-1])
	return 1 + lcs(X, Y, m-1, n-1);
	else
	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
	return (a > b)? a : b;
}

public static void main(String[] args)
{
	LongestCommonSubsequence lcs = new LongestCommonSubsequence();
	String s1 = "AGGTAB";
	String s2 = "GXTXAYB";

	char[] X=s1.toCharArray();
	char[] Y=s2.toCharArray();
	int m = X.length;
	int n = Y.length;

	System.out.println("Length of LCS is" + " " +
								lcs.lcs( X, Y, m, n ) );
}

}

// This Code is Contributed by Saket Kumar

# A Naive recursive Python implementation of LCS problem

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

	if m == 0 or n == 0:
	return 0;
	elif X[m-1] == Y[n-1]:
	return 1 + lcs(X, Y, m-1, n-1);
	else:
	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));


# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X , Y, len(X), len(Y))

/* C# Naive recursive implementation of LCS problem */
using System;

class GFG
{
	

	/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	static int lcs( char[] X, char[] Y, int m, int n )
	{
		if (m == 0 || n == 0)
		return 0;
		if (X[m - 1] == Y[n - 1])
		return 1 + lcs(X, Y, m - 1, n - 1);
		else
		return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
	}
	
	/* Utility function to get max of 2 integers */
	static int max(int a, int b)
	{
		return (a > b)? a : b;
	}
	
	public static void Main()
	{
		String s1 = "AGGTAB";
		String s2 = "GXTXAYB";
	
		char[] X=s1.ToCharArray();
		char[] Y=s2.ToCharArray();
		int m = X.Length;
		int n = Y.Length;
	
		Console.Write("Length of LCS is" + " "
					+lcs( X, Y, m, n ) );
	}
}
// This code is Contributed by Sam007

<?php
// A Naive recursive PHP
// implementation of LCS problem
function lcs($X, $Y, $m, $n)
{
	if($m == 0 || $n == 0)
	return 0;
	else if ($X[$m - 1] == $Y[$n - 1])
		return 1 + lcs($X, $Y,
					$m - 1, $n - 1);
	else
		return max(lcs($X, $Y, $m, $n - 1),
				lcs($X, $Y, $m - 1, $n));
}

// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is ";
echo lcs($X , $Y, strlen($X),
				strlen($Y));

// This code is contributed
// by Shivi_Aggarwal
?>

<script>
/* A Naive recursive implementation of LCS problem in java*/

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
function lcs( X, Y , m , n )
{
	if (m == 0 || n == 0)
	return 0;
	if (X[m-1] == Y[n-1])
	return 1 + lcs(X, Y, m-1, n-1);
	else
	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
function max(a , b)
{
	return (a > b)? a : b;
}



	var s1 = "AGGTAB";
	var s2 = "GXTXAYB";

	var X=s1;
	var Y=s2;
	var m = X.length;
	var n = Y.length;

	document.write("Length of LCS is" + " " +
								lcs( X, Y, m, n ) );

// This code contributed by umadevi9616
</script>

Выход:

Length of LCS is 4

Временная сложность вышеупомянутого наивного рекурсивного подхода составляет O(2^n) в наихудшем случае, а наихудший случай возникает, когда все символы X и Y не совпадают, т. Е. длина LCS равна 0.

Учитывая приведенную выше реализацию, ниже приведено дерево частичной рекурсии для входных строк “AXYT” и “AYZX”

                         lcs("AXYT", "AYZX")
                       /                 
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /                              /               
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

В приведенном выше дереве частичной рекурсии lcs(“AXY”, “AYZ”) решается дважды. Если мы нарисуем полное дерево рекурсии, то увидим, что существует множество подзадач, которые решаются снова и снова. Таким образом, эта проблема имеет свойство перекрывающейся подструктуры, и повторного вычисления одних и тех же подзадач можно избежать либо с помощью запоминания, либо с помощью таблиц. Ниже приведена табличная реализация проблемы LCS.

def lcs(s1 , s2):
m, n = len(s1), len(s2)
prev, cur = [0]*(n+1), [0]*(n+1)
for i in range(1, m+1):
	for j in range(1, n+1):
		if s1[i-1] == s2[j-1]:
			cur[j] = 1 + prev[j-1]
		else:
			if cur[j-1] > prev[j]:
				cur[j] = cur[j-1]
			else:
				cur[j] = prev[j]
	cur, prev = prev, cur
return prev[n]

#end of function lcs


# Driver program to test the above function
s1 = "AGGTAB"
s2 = "GXTXAYB"
print("Length of LCS is ", lcs(s1, s2))
# BY PRASHANT SHEKHAR MISHRA

/* Dynamic Programming C implementation of LCS problem */
#include<bits/stdc++.h>

int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
int i, j;

/* Following steps build L[m+1][n+1] in bottom up fashion. Note
	that L[i][j] contains length of LCS of X[0..i-1] and 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]);
	}
}
	
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
	return (a > b)? a : b;
}

/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";

int m = strlen(X);
int n = strlen(Y);

printf("Length of LCS is %d", lcs( X, Y, m, n ) );

return 0;
}

/* Dynamic Programming Java implementation of LCS problem */
public class LongestCommonSubsequence
{

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char[] X, char[] Y, int m, int n )
{
	int L[][] = new int[m+1][n+1];

	/* Following steps build L[m+1][n+1] in bottom up fashion. Note
		that L[i][j] contains length of LCS of X[0..i-1] and 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]);
	}
	}
return L[m][n];
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
	return (a > b)? a : b;
}

public static void main(String[] args)
{
	LongestCommonSubsequence lcs = new LongestCommonSubsequence();
	String s1 = "AGGTAB";
	String s2 = "GXTXAYB";

	char[] X=s1.toCharArray();
	char[] Y=s2.toCharArray();
	int m = X.length;
	int n = Y.length;

	System.out.println("Length of LCS is" + " " +
								lcs.lcs( X, Y, m, n ) );
}

}

// This Code is Contributed by Saket Kumar

# Dynamic Programming implementation of LCS problem

def lcs(X , Y):
	# find the length of the strings
	m = len(X)
	n = len(Y)

	# declaring the array for storing the dp values
	L = [[None]*(n+1) for i in xrange(m+1)]

	"""Following steps build L[m+1][n+1] in bottom up fashion
	Note: L[i][j] contains length of LCS of X[0..i-1]
	and Y[0..j-1]"""
	for i in range(m+1):
		for j in range(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])

	# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
	return L[m][n]
#end of function lcs


# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// Dynamic Programming C# implementation
// of LCS problem
using System;

class GFG
{

	/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	static int lcs( char[] X, char[] Y, int m, int n )
	{
		int [,]L = new int[m+1,n+1];
	
		/* Following steps build L[m+1][n+1]
		in bottom up fashion. Note
		that L[i][j] contains length of
		LCS of X[0..i-1] and 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]);
			}
		}
		return L[m, n];
	}
	
	/* Utility function to get max of 2 integers */
	static int max(int a, int b)
	{
		return (a > b)? a : b;
	}
	
	// Driver code
	public static void Main()
	{
		
		String s1 = "AGGTAB";
		String s2 = "GXTXAYB";
	
		char[] X=s1.ToCharArray();
		char[] Y=s2.ToCharArray();
		int m = X.Length;
		int n = Y.Length;
	
		Console.Write("Length of LCS is" + " " +lcs( X, Y, m, n ) );
	}
}
// This Code is Contributed by Sam007

<?php
// Dynamic Programming C#
// implementation of LCS problem
function lcs($X , $Y)
{
// find the length of the strings
$m = strlen($X);
$n = strlen($Y) ;

// declaring the array for
// storing the dp values

/*Following steps build L[m+1][n+1]
in bottom up fashion .
Note: L[i][j] contains length of
LCS of X[0..i-1] and 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]);
}
}

// L[m][n] contains the length of
// LCS of X[0..n-1] & Y[0..m-1]

return $L[$m][$n];
}

// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is ";
echo lcs($X, $Y);

// This code is contributed
// by Shivi_Aggarwal
?>

<script>

// Dynamic Programming Java implementation of LCS problem

// Utility function to get max of 2 integers
function max(a, b)
{
	if (a > b)
		return a;
	else
		return b;
}

// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs(X, Y, m, n)
{
	var L = new Array(m + 1);
	for(var i = 0; i < L.length; i++)
	{
		L[i] = new Array(n + 1);
	}
	var i, j;
	
	/* Following steps build L[m+1][n+1] in
	bottom up fashion. Note that L[i][j]
	contains length of LCS of X[0..i-1]
	and 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]);
		}
	}
	
	/* L[m][n] contains length of LCS
	for X[0..n-1] and Y[0..m-1] */
	return L[m][n];
}

// Driver code
var x = "AGGTAB";
var y = "GXTXAYB";

var m = x.length;
var n = y.length;

document.write("Length of LCS is " + lcs(x, y, m, n));

// This code is contributed by akshitsaxenaa09

</script>

Выход:

Length of LCS is 4

Временная сложность вышеупомянутой реализации составляет O(mn), что намного лучше, чем временная сложность наихудшего случая наивной рекурсивной реализации.
Приведенный выше алгоритм/код возвращает только длину LCS. Пожалуйста, смотрите следующий пост для печати LCS.

Метки: Самая длинная общая подпоследовательность | DP-4

Примеры:

1) Оптимальная подструктура:

Примеры:

2) Перекрывающиеся подзадачи:

Выход:

Выход:

Вам также может понравиться

Подсчитайте столбец таблицы SQL с помощью Python

MySQL | Общие запросы MySQL

Цикл JavaScript While