Skip to main content

Longest common subsequence

In computer science, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The longest common subsequence (LCS) of two or more sequences is the longest subsequence that is present in all the given sequences in the same relative order.

For example, let's consider two sequences: "ACBDEA" and "ABCDA". The common subsequences are "A", "B", "C", "D", "E", "AB", "AC", "AD", "AE", "BC", "BD", and "DA". Out of these subsequences, the longest common subsequence is "ABDA", which appears in both the given sequences in the same order.

The problem of finding the longest common subsequence is a well-studied problem in computer science, and it has applications in fields such as bioinformatics, data compression, and version control systems.

Program Solution

// C Program 
// Longest common subsequence
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Returns the length of common substring
int lcs(const char *s1 , const char *s2, int n1, int n2, int i, int j)
{
	if (i == n1 || j == n2)
	{
		// When string length exceeds
		return 0;
	}
	else if (s1[i] == s2[j])
	{
		// When similar characters meet
		return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
	}
	else
	{
		// Through recursively find similar characters
		return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
	}
}
int main(int argc, char
	const *argv[])
{
	const char *s1 = "AABCAEGDS";
	const char *s2 = "ADBSEDF";
	// Get the size of string
	int n1 = strlen(s1);
	int n2 = strlen(s2);
	int ans = lcs(s1, s2, n1, n2, 0, 0);
	// Display length of common substring
	printf("\n %d\n", ans);
	return 0;
}

Output

 4
/*
  Java Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	public int lcs(String s1, String s2, int n1, int n2, int i, int j)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1.charAt(i) == s2.charAt(j))
		{
			// When similar characters meet
			return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
	public static void main(String[] args)
	{
		LongestSubsequence task = new LongestSubsequence();
		String s1 = "AABCAEGDS";
		String s2 = "ADBSEDF";
		// Get the size of string
		int n1 = s1.length();
		int n2 = s2.length();
		int ans = task.lcs(s1, s2, n1, n2, 0, 0);
		// Display length of common substring
		System.out.print("\n " + ans + "\n");
	}
}

Output

 4
// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
  C++ Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	public:
		// Returns the max value of given two numbers
		int maxValue(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			else
			{
				return b;
			}
		}
	// Returns the length of common substring
	int lcs(string s1, string s2, int n1, int n2, int i, int j)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			return 1 + this->lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this->maxValue(this->lcs(s1, s2, n1, n2, i + 1, j), this->lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
};
int main()
{
	LongestSubsequence task = LongestSubsequence();
	string s1 = "AABCAEGDS";
	string s2 = "ADBSEDF";
	// Get the size of string
	int n1 = s1.size();
	int n2 = s2.size();
	int ans = task.lcs(s1, s2, n1, n2, 0, 0);
	// Display length of common substring
	cout << "\n " << ans << "\n";
	return 0;
}

Output

 4
// Include namespace system
using System;
/*
  C# Program for
  Longest common subsequence
*/
public class LongestSubsequence
{
	// Returns the max value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	public int lcs(String s1, String s2, int n1, int n2, int i, int j)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
	public static void Main(String[] args)
	{
		LongestSubsequence task = new LongestSubsequence();
		String s1 = "AABCAEGDS";
		String s2 = "ADBSEDF";
		// Get the size of string
		int n1 = s1.Length;
		int n2 = s2.Length;
		int ans = task.lcs(s1, s2, n1, n2, 0, 0);
		// Display length of common substring
		Console.Write("\n " + ans + "\n");
	}
}

Output

 4
<?php
/*
  Php Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Returns the length of common substring
	public	function lcs($s1, $s2, $n1, $n2, $i, $j)
	{
		if ($i == $n1 || $j == $n2)
		{
			// When string length exceeds
			return 0;
		}
		else if ($s1[$i] == $s2[$j])
		{
			// When similar characters meet
			return 1 + $this->lcs($s1, $s2, $n1, $n2, $i + 1, $j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return $this->maxValue($this->lcs($s1, $s2, $n1, $n2, $i + 1, $j), $this->lcs($s1, $s2, $n1, $n2, $i, $j + 1));
		}
	}
}

function main()
{
	$task = new LongestSubsequence();
	$s1 = "AABCAEGDS";
	$s2 = "ADBSEDF";
	// Get the size of string
	$n1 = strlen($s1);
	$n2 = strlen($s2);
	$ans = $task->lcs($s1, $s2, $n1, $n2, 0, 0);
	// Display length of common substring
	echo "\n ". $ans ."\n";
}
main();

Output

 4
/*
  Node Js Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	lcs(s1, s2, n1, n2, i, j)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
}

function main()
{
	var task = new LongestSubsequence();
	var s1 = "AABCAEGDS";
	var s2 = "ADBSEDF";
	// Get the size of string
	var n1 = s1.length;
	var n2 = s2.length;
	var ans = task.lcs(s1, s2, n1, n2, 0, 0);
	// Display length of common substring
	process.stdout.write("\n " + ans + "\n");
}
main();

Output

 4
#   Python 3 Program for
#   Longest common subsequence

class LongestSubsequence :
	#  Returns the max value of given two numbers
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Returns the length of common substring
	def lcs(self, s1, s2, n1, n2, i, j) :
		if (i == n1 or j == n2) :
			#  When string length exceeds
			return 0
		
		elif(s1[i] == s2[j]) :
			#  When similar characters meet
			return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1)
		else :
			#  Through recursively find similar characters
			return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1))
		
	

def main() :
	task = LongestSubsequence()
	s1 = "AABCAEGDS"
	s2 = "ADBSEDF"
	#  Get the size of string
	n1 = len(s1)
	n2 = len(s2)
	ans = task.lcs(s1, s2, n1, n2, 0, 0)
	#  Display length of common substring
	print("\n ", ans )

if __name__ == "__main__": main()

Output

  4
#   Ruby Program for
#   Longest common subsequence

class LongestSubsequence 
	#  Returns the max value of given two numbers
	def maxValue(a, b) 
		if (a > b) 
			return a
		else 
			return b
		end

	end

	#  Returns the length of common substring
	def lcs(s1, s2, n1, n2, i, j) 
		if (i == n1 || j == n2) 
			#  When string length exceeds
			return 0
		elsif(s1[i] == s2[j]) 
			#  When similar characters meet
			return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1)
		else 
			#  Through recursively find similar characters
			return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1))
		end

	end

end

def main() 
	task = LongestSubsequence.new()
	s1 = "AABCAEGDS"
	s2 = "ADBSEDF"
	#  Get the size of string
	n1 = s1.length()
	n2 = s2.length()
	ans = task.lcs(s1, s2, n1, n2, 0, 0)
	#  Display length of common substring
	print("\n ", ans ,"\n")
end

main()

Output

 4

/*
  Scala Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	def lcs(s1: String, s2: String, n1: Int, n2: Int, i: Int, j: Int): Int = {
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1(i) == s2(j))
		{
			// When similar characters meet
			return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LongestSubsequence = new LongestSubsequence();
		var s1: String = "AABCAEGDS";
		var s2: String = "ADBSEDF";
		// Get the size of string
		var n1: Int = s1.length();
		var n2: Int = s2.length();
		var ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
		// Display length of common substring
		print("\n " + ans + "\n");
	}
}

Output

 4
/*
  Swift 4 Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	func maxValue(_ a: Int, _ b: Int)->Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	func lcs(_ s1: String, _ s2: String, _ n1: Int, _ n2: Int, _ i: Int, _ j: Int)->Int
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (Array(s1)[i] == Array(s2)[j])
		{
			// When similar characters meet
			return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
}
func main()
{
	let task: LongestSubsequence = LongestSubsequence();
	let s1: String = "AABCAEGDS";
	let s2: String = "ADBSEDF";
	// Get the size of string
	let n1: Int = s1.count;
	let n2: Int = s2.count;
	let ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
	// Display length of common substring
	print("\n ", ans );
}
main();

Output

  4
/*
  Kotlin Program for
  Longest common subsequence
*/
class LongestSubsequence
{
	// Returns the max value of given two numbers
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Returns the length of common substring
	fun lcs(s1: String, s2: String, n1: Int, n2: Int, i: Int, j: Int): Int
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return 0;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: LongestSubsequence = LongestSubsequence();
	var s1: String = "AABCAEGDS";
	var s2: String = "ADBSEDF";
	// Get the size of string
	var n1: Int = s1.count();
	var n2: Int = s2.count();
	var ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
	// Display length of common substring
	print("\n " + ans + "\n");
}

Output

 4
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment