LCS (Самая длинная общая подпоследовательность) из трех строк

ProgramBox

LCS (Самая длинная общая подпоследовательность) из трех строк

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

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

Примеры:

Input : str1 = "geeks" 
 str2 = "geeksfor" 
 str3 = "geeksforgeeks"
Output : 5
Longest common subsequence is "geeks"
i.e., length = 5

Input : str1 = "abcd1e2" 
 str2 = "bc12ea" 
 str3 = "bd1ea"
Output : 3
Longest common subsequence is "b1e" 
i.e. length = 3.

Эта проблема является просто расширением LCS, пусть входные последовательности будут X[0..m-1], Y[0..n-1] и Z[0..o-1] длин m, n и o соответственно. И пусть L(X[0..m-1], Y[0..n-1], Z[0..o-1]) — длины LC трех последовательностей X, Y и Z. Ниже приводится реализация:

The idea is to take a 3D array to store the 
length of common subsequence in all 3 given 
sequences i. e., L[m + 1][n + 1][o + 1]

1- If any of the string is empty then there
 is no common subsequence at all then
 L[i][j][k] = 0

2- If the characters of all sequences match
 (or X[i] == Y[j] ==Z[k]) then
 L[i][j][k] = 1 + L[i-1][j-1][k-1]

3- If the characters of both sequences do 
 not match (or X[i] != Y[j] || X[i] != Z[k] 
 || Y[j] !=Z[k]) then
 L[i][j][k] = max(L[i-1][j][k], 
 L[i][j-1][k], 
 L[i][j][k-1])

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

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;

/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
int lcsOf3( string X, string Y, string Z, int m,
							int n, int o)
{
	int L[m+1][n+1][o+1];

	/* Following steps build L[m+1][n+1][o+1] in
	bottom up fashion. Note that L[i][j][k]
	contains length of LCS of X[0..i-1] and
	Y[0..j-1] and Z[0.....k-1]*/
	for (int i=0; i<=m; i++)
	{
		for (int j=0; j<=n; j++)
		{
			for (int k=0; k<=o; k++)
			{
				if (i == 0 || j == 0||k==0)
					L[i][j][k] = 0;

				else if (X[i-1] == Y[j-1] && X[i-1]==Z[k-1])
					L[i][j][k] = L[i-1][j-1][k-1] + 1;

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

	/* L[m][n][o] contains length of LCS for
	X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
	return L[m][n][o];
}

/* Driver program to test above function */
int main()
{
	string X = "AGGT12";
	string Y = "12TXAYB";
	string Z = "12XBA";

	int m = X.length();
	int n = Y.length();
	int o = Z.length();

	cout << "Length of LCS is " << lcsOf3(X, Y,
									Z, m, n, o);

	return 0;
}

// Java program to find LCS of three strings
public class LCS_3Strings {
	
	/* Returns length of LCS for X[0..m-1], Y[0..n-1]
	and Z[0..o-1] */
	static int lcsOf3(String X, String Y, String Z, int m,
								int n, int o)
	{
		int[][][] L = new int[m+1][n+1][o+1];
	
		/* Following steps build L[m+1][n+1][o+1] in
		bottom up fashion. Note that L[i][j][k]
		contains length of LCS of X[0..i-1] and
		Y[0..j-1] and Z[0.....k-1]*/
		for (int i=0; i<=m; i++)
		{
			for (int j=0; j<=n; j++)
			{
				for (int k=0; k<=o; k++)
				{
					if (i == 0 || j == 0||k==0)
						L[i][j][k] = 0;
	
					else if (X.charAt(i - 1) == Y.charAt(j - 1)
								&& X.charAt(i - 1)==Z.charAt(k - 1))
						L[i][j][k] = L[i-1][j-1][k-1] + 1;
	
					else
						L[i][j][k] = Math.max(Math.max(L[i-1][j][k],
											L[i][j-1][k]),
										L[i][j][k-1]);
				}
			}
		}
	
		/* L[m][n][o] contains length of LCS for
		X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
		return L[m][n][o];
	}
	
	/* Driver program to test above function */
	public static void main(String args[])
	{
		String X = "AGGT12";
		String Y = "12TXAYB";
		String Z = "12XBA";
	
		int m = X.length();
		int n = Y.length();
		int o = Z.length();
	
		System.out.println("Length of LCS is " +
								lcsOf3(X, Y,Z, m, n, o));
	
	}
}
// This code is contributed by Sumit Ghosh

# Python program to find
# LCS of three strings

# Returns length of LCS
# for X[0..m-1], Y[0..n-1]
# and Z[0..o-1]
def lcsOf3(X, Y, Z, m, n, o):
	
	L = [[[0 for i in range(o+1)] for j in range(n+1)]
		for k in range(m+1)]

	''' Following steps build L[m+1][n+1][o+1] in
	bottom up fashion. Note that L[i][j][k]
	contains length of LCS of X[0..i-1] and
	Y[0..j-1] and Z[0.....k-1] '''
	for i in range(m+1):
		for j in range(n+1):
			for k in range(o+1):
				if (i == 0 or j == 0 or k == 0):
					L[i][j][k] = 0
					
				elif (X[i-1] == Y[j-1] and
					X[i-1] == Z[k-1]):
					L[i][j][k] = L[i-1][j-1][k-1] + 1

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

	# L[m][n][o] contains length of LCS for
	# X[0..n-1] and Y[0..m-1] and Z[0..o-1]
	return L[m][n][o]

# Driver program to test above function

X = 'AGGT12'
Y = '12TXAYB'
Z = '12XBA'

m = len(X)
n = len(Y)
o = len(Z)

print('Length of LCS is', lcsOf3(X, Y, Z, m, n, o))

# This code is contributed by Soumen Ghosh.

// C# program to find
// LCS of three strings
using System;

class GFG
{
	
	/* Returns length of LCS
	for X[0..m-1], Y[0..n-1]
	and Z[0..o-1] */
	static int lcsOf3(String X, String Y,
					String Z, int m,
					int n, int o)
	{
		int [,,]L = new int[m + 1,
							n + 1, o + 1];
	
		/* Following steps build
		L[m+1][n+1][o+1] in bottom
		up fashion. Note that
		L[i][j][k] contains length
		of LCS of X[0..i-1] and
		Y[0..j-1] and Z[0.....k-1]*/
		for (int i = 0; i <= m; i++)
		{
			for (int j = 0; j <= n; j++)
			{
				for (int k = 0; k <= o; k++)
				{
					if (i == 0 ||
						j == 0 || k == 0)
						L[i, j, k] = 0;
	
					else if (X[i - 1] == Y[j - 1] &&
							X[i - 1] == Z[k - 1])
						L[i, j, k] = L[i - 1,
									j - 1,
									k - 1] + 1;
	
					else
						L[i, j, k] = Math.Max(Math.Max(L[i - 1, j, k],
													L[i, j - 1, k]),
													L[i, j, k - 1]);
				}
			}
		}
	
		/* L[m][n][o] contains length
		of LCS for X[0..n-1] and
		Y[0..m-1] and Z[0..o-1]*/
		return L[m, n, o];
	}
	
	// Driver Code
	public static void Main()
	{
		string X = "AGGT12";
		string Y = "12TXAYB";
		string Z = "12XBA";
	
		int m = X.Length;
		int n = Y.Length;
		int o = Z.Length;
	
		Console.Write("Length of LCS is " +
					lcsOf3(X, Y, Z, m, n, o));
	}
}

// This code is contributed
// by shiv_bhakt.

<?php
// PHP program to find
// LCS of three strings

/* Returns length of LCS for
X[0..m-1], Y[0..n-1] and Z[0..o-1] */
function lcsOf3($X, $Y, $Z,
				$m, $n, $o)
{
	$L[$m + 1][$n + 1][$o + 1] = array(array(array()));

	/* Following steps build
	L[m+1][n+1][o+1] in bottom
	up fashion. Note that
	L[i][j][k] contains length
	of LCS of X[0..i-1] and
	Y[0..j-1] and Z[0.....k-1]*/
	for ($i = 0; $i <= $m; $i++)
	{
		for ($j = 0; $j <= $n; $j++)
		{
			for ($k = 0; $k <= $o; $k++)
			{
				if ($i == 0 || $j == 0||$k == 0)
					$L[$i][$j][$k] = 0;

				else if ($X[$i - 1] == $Y[$j - 1] &&
						$X[$i - 1] == $Z[$k - 1])
					$L[$i][$j][$k] = $L[$i - 1][$j - 1][$k - 1] + 1;

				else
					$L[$i][$j][$k] = max(max($L[$i - 1][$j][$k],
											$L[$i][$j - 1][$k]),
											$L[$i][$j][$k - 1]);
			}
		}
	}

	/* L[m][n][o] contains length
	of LCS for X[0..n-1] and
	Y[0..m-1] and Z[0..o-1]*/
	return $L[$m][$n][$o];
}

// Driver code
$X = "AGGT12";
$Y = "12TXAYB";
$Z = "12XBA";

$m = strlen($X);
$n = strlen($Y);
$o = strlen($Z);

echo "Length of LCS is " .
	lcsOf3($X, $Y, $Z,
			$m, $n, $o);

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

<script>
// Javascript program to find LCS of three strings
	
	/* Returns length of LCS for X[0..m-1], Y[0..n-1]
	and Z[0..o-1] */
	function lcsOf3(X,Y,Z,m,n,o)
	{
		let L = new Array(m + 1);
		for(let i = 0; i < m + 1; i++)
		{
			L[i] = new Array(n + 1);
			for(let j = 0; j < n + 1; j++)
			{
				L[i][j] = new Array(o + 1);
				for(let k = 0; k < o + 1; k++)
				{
					L[i][j][k] = 0;
				}
			}
		}
		
		/* Following steps build L[m+1][n+1][o+1] in
		bottom up fashion. Note that L[i][j][k]
		contains length of LCS of X[0..i-1] and
		Y[0..j-1] and Z[0.....k-1]*/
		for (let i = 0; i <= m; i++)
		{
			for (let j = 0; j <= n; j++)
			{
				for (let k = 0; k <= o; k++)
				{
					if (i == 0 || j == 0 || k == 0)
						L[i][j][k] = 0;
		
					else if (X[i - 1] == Y[j - 1]
								&& X[i - 1] == Z[k - 1])
						L[i][j][k] = L[i - 1][j - 1][k - 1] + 1;
		
					else
						L[i][j][k] = Math.max(Math.max(L[i - 1][j][k],
											L[i][j - 1][k]),
										L[i][j][k - 1]);
				}
			}
		}
		
		/* L[m][n][o] contains length of LCS for
		X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
		return L[m][n][o];
	}
	
	/* Driver program to test above function */
	let X = "AGGT12";
	let Y = "12TXAYB";
	let Z = "12XBA";
	let m = X.length;
	let n = Y.length;
	let o = Z.length;
	
	document.write("Length of LCS is " +
							lcsOf3(X, Y,Z, m, n, o));
	
	// This code is contributed by avanitrachhadiya2155
</script>

Выход:

Length of LCS is 2

Другой подход: (Используя рекурсию)

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;

	string X = "AGGT12";
	string Y = "12TXAYB";
	string Z = "12XBA";

int dp[100][100][100];

/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
int lcsOf3(int i, int j,int k)
{
	if(i==-1||j==-1||k==-1)
		return 0;
	if(dp[i][j][k]!=-1)
		return dp[i][j][k];
	
	if(X[i]==Y[j] && Y[j]==Z[k])
		return dp[i][j][k] = 1+lcsOf3(i-1,j-1,k-1);
	else
		return dp[i][j][k] = max(max(lcsOf3(i-1,j,k),
							lcsOf3(i,j-1,k)),lcsOf3(i,j,k-1));
}

// Driver code
int main()
{
	memset(dp, -1,sizeof(dp));
	int m = X.length();
	int n = Y.length();
	int o = Z.length();

	cout << "Length of LCS is " << lcsOf3(m-1,n-1,o-1);
// this code is contributed by Kushdeep Mittal
}

// Java program to find LCS of three strings
class GFG
{

	static String X = "AGGT12";
	static String Y = "12TXAYB";
	static String Z = "12XBA";

	static int[][][] dp = new int[100][100][100];

	/* Returns length of LCS for X[0..m-1],
	Y[0..n-1] and Z[0..o-1] */
	static int lcsOf3(int i, int j, int k)
	{
		if (i == -1 || j == -1 || k == -1)
		{
			return 0;
		}
		if (dp[i][j][k] != -1)
		{
			return dp[i][j][k];
		}

		if (X.charAt(i) == Y.charAt(j) &&
			Y.charAt(j) == Z.charAt(k))
		{
			return dp[i][j][k] = 1 + lcsOf3(i - 1, j - 1, k - 1);
		} else {
			return dp[i][j][k] = Math.max(Math.max(lcsOf3(i - 1, j, k),
								lcsOf3(i, j - 1, k)),
								lcsOf3(i, j, k - 1));
		}
	}

	// Driver code
	public static void main(String[] args)
	{

		for (int i = 0; i < 100; i++)
		{
			for (int j = 0; j < 100; j++)
			{
				for (int k = 0; k < 100; k++)
				{
					dp[i][j][k] = -1;
				}
			}
		}
		int m = X.length();
		int n = Y.length();
		int o = Z.length();

		System.out.print("Length of LCS is "
				+ lcsOf3(m - 1, n - 1, o - 1));
	}
}

// This code has been contributed by 29AjayKumar

# Python3 program to find LCS of
# three strings
X = "AGGT12"
Y = "12TXAYB"
Z = "12XBA"

dp = [[[-1 for i in range(100)]
		for j in range(100)]
		for k in range(100)]
		
# Returns length of LCS for
# X[0..m-1], Y[0..n-1] and Z[0..o-1]
def lcsOf3(i, j, k) :

	if(i == -1 or j == -1 or k == -1) :
		return 0
		
	if(dp[i][j][k] != -1) :
		return dp[i][j][k]
	
	if(X[i] == Y[j] and Y[j] == Z[k]) :
		dp[i][j][k] = 1 + lcsOf3(i - 1,
								j - 1, k - 1)
		return dp[i][j][k]
		
	else :
		dp[i][j][k] = max(max(lcsOf3(i - 1, j, k),
							lcsOf3(i, j - 1, k)),
							lcsOf3(i, j, k - 1))
		
		return dp[i][j][k]

# Driver code
if __name__ == "__main__" :
	m = len(X)
	n = len(Y)
	o = len(Z)

	print("Length of LCS is",
		lcsOf3(m - 1, n - 1, o - 1))
	
# This code is contributed by Ryuga

// C# program to find LCS of three strings
using System;

class GFG
{
static string X = "AGGT12";
static string Y = "12TXAYB";
static string Z = "12XBA";

static int[,,] dp = new int[100, 100, 100];

/* Returns length of LCS for X[0..m-1],
Y[0..n-1] and Z[0..o-1] */
static int lcsOf3(int i, int j, int k)
{
	if(i == -1 || j == -1 || k == -1)
		return 0;
	if(dp[i, j, k] != -1)
		return dp[i, j, k];
	
	if(X[i] == Y[j] && Y[j] == Z[k])
		return dp[i, j, k] = 1 + lcsOf3(i - 1, j - 1, k - 1);
	else
		return dp[i, j, k] = Math.Max(Math.Max(lcsOf3(i - 1, j, k),
											lcsOf3(i, j - 1, k)),
											lcsOf3(i, j, k - 1));
}

// Driver code
static void Main()
{
	for(int i = 0; i < 100; i++)
		for(int j = 0; j < 100; j++)
			for(int k = 0; k < 100; k++)
				dp[i, j, k] = -1;
	int m = X.Length;
	int n = Y.Length;
	int o = Z.Length;

	Console.Write("Length of LCS is " +
				lcsOf3(m - 1, n - 1, o - 1));
}
}

// This code is contributed by DrRoot_

<?php
// PHP program to find LCS of three strings

	$X = "AGGT12";
	$Y = "12TXAYB";
	$Z = "12XBA";

	$dp=array_fill(0, 100, array_fill(0, 100, array_fill(0, 100, -1)));

/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
function lcsOf3($i, $j, $k)
{
	global $dp, $X, $Y, $Z;
	if($i == -1 || $j == -1 || $k == -1)
		return 0;
	if($dp[$i][$j][$k] != -1)
		return $dp[$i][$j][$k];
	
	if($X[$i] == $Y[$j] && $Y[$j] == $Z[$k])
		return $dp[$i][$j][$k] = 1+lcsOf3($i - 1, $j - 1, $k - 1);
	else
		return $dp[$i][$j][$k] = max(max(lcsOf3($i - 1, $j, $k),
							lcsOf3($i, $j - 1, $k)), lcsOf3($i, $j, $k - 1));
}

// Driver code
	$m = strlen($X);
	$n = strlen($Y);
	$o = strlen($Z);

	echo "Length of LCS is ".lcsOf3($m - 1, $n - 1, $o - 1);

// This code is contributed by mits

?>

<script>
// Java program to find LCS of three strings

let X = "AGGT12";
let Y = "12TXAYB";
let Z = "12XBA";

let dp = new Array(100);
for(let i=0;i<100;i++)
{
	dp[i]=new Array(100);
	for(let j=0;j<100;j++)
	{
		dp[i][j]=new Array(100);
		for(let k=0;k<100;k++)
		{
			dp[i][j][k]=-1;
		}
	}
}

/* Returns length of LCS for X[0..m-1],
	Y[0..n-1] and Z[0..o-1] */
function lcsOf3(i,j,k)
{
	if (i == -1 || j == -1 || k == -1)
		{
			return 0;
		}
		if (dp[i][j][k] != -1)
		{
			return dp[i][j][k];
		}

		if (X[i] == Y[j] &&
			Y[j] == Z[k])
		{
			return dp[i][j][k] = 1 + lcsOf3(i - 1, j - 1, k - 1);
		} else {
			return dp[i][j][k] = Math.max(Math.max(lcsOf3(i - 1, j, k),
								lcsOf3(i, j - 1, k)),
								lcsOf3(i, j, k - 1));
		}
}

// Driver code

		let m = X.length;
		let n = Y.length;
		let o = Z.length;

		document.write("Length of LCS is "
				+ lcsOf3(m - 1, n - 1, o - 1));


// This code is contributed by rag2127
</script>

Выход:

Length of LCS is 2

Метки: LCS (Самая длинная общая подпоследовательность) из трех строк

Примеры:

Выход:

Другой подход: (Используя рекурсию)

Выход:

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

Сочетания клавиш в оболочке IPython

Частные переменные в Python

Python: MySQL создать таблицу