Блог

Главная - C# язык программирования - LCS (Самая длинная общая подпоследовательность) из трех строк
You are currently viewing LCS (Самая длинная общая подпоследовательность) из трех строк

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

Учитывая, что все 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

Метки: