Skip to main content

Print all longest common subsequence

Here given code implementation process.

// C Program 
// Print all longest common subsequence 
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int max_value(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Returns the length of common substring
int lcs_length(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_length(s1, s2, n1, n2, i + 1, j + 1);
	}
	else
	{
		// Through recursively find similar characters
		return max_value(lcs_length(s1, s2, n1, n2, i + 1, j), lcs_length(s1, s2, n1, n2, i, j + 1));
	}
}
// Display the result
void print_result(const char *s1, int visit[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		if (visit[i] == 1)
		{
			printf("%c", s1[i]);
		}
	}
	printf("\n");
}
// Print the all common subsequence in longest length 
int find_lcs(const char *s1 , const char *s2, int visit[], int n1, int n2, int i, int j, int k, int length)
{
	if (i == n1 || j == n2)
	{
		// When string length exceeds
		return 0;
	}
	else if (s1[i] == s2[j])
	{
		// When similar characters meet
		visit[i] = 1;
		if (k + 1 == length)
		{
			print_result(s1, visit, n1);
			visit[i] = 0;
			return 1;
		}
		else
		{
			find_lcs(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
		}
		visit[i] = 0;
	}
	else
	{
		// Through recursively find similar characters
		if (find_lcs(s1, s2, visit, n1, n2, i + 1, j, k, length) || find_lcs(s1, s2, visit, n1, n2, i, j + 1, k, length))
		{
			return 1;
		}
	}
	return 0;
}
// Handles the request of display longest common subsequence
void lcs(const char *s1 , const char *s2)
{
	// Get the size of string
	int n1 = strlen(s1);
	int n2 = strlen(s2);
	// First find the length of LCS
	int length = lcs_length(s1, s2, n1, n2, 0, 0);
	if (length > 0)
	{
		int visit[n1];
		for (int i = 0; i < n1; ++i)
		{
			visit[i] = 0;
		}
		// Print all longest common subsequence of given two strings
		find_lcs(s1, s2, visit, n1, n2, 0, 0, 0, length);
	}
}
int main(int argc, char
	const *argv[])
{
	// Given input strings
	const char *s1 = "XYZXYZXXZ";
	const char *s2 = "XZYXZYX";
	lcs(s1, s2);
	return 0;
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
/*
  Java Program for
  Print all 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 lcsLength(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 + lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return maxValue(lcsLength(s1, s2, n1, n2, i + 1, j), lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	public void printResult(String s, boolean[] visit, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			if (visit[i] == true)
			{
				System.out.print(s.charAt(i));
			}
		}
		System.out.print("\n");
	}
	// Print the all common subsequence in longest length 
	public boolean findLCS(String s1, String s2, boolean[] visit, int n1, int n2, int i, int j, int k, int length)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1.charAt(i) == s2.charAt(j))
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	public void lcs(String s1, String s2)
	{
		// Get the size of string
		int n1 = s1.length();
		int n2 = s2.length();
		// First find the length of LCS
		int length = lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			boolean[] visit = new boolean[n1];
			for (int i = 0; i < length; ++i)
			{
				visit[i] = false;
			}
			// Print all longest common subsequence of given two strings
			findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
	public static void main(String[] args)
	{
		LongestSubsequence task = new LongestSubsequence();
		String s1 = "XYZXYZXXZ";
		String s2 = "XZYXZYX";
		task.lcs(s1, s2);
	}
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
  C++ Program for
  Print all 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 lcsLength(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->lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this->maxValue(this->lcsLength(s1, s2, n1, n2, i + 1, j), this->lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	void printResult(string s, bool visit[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			if (visit[i] == true)
			{
				cout << s[i];
			}
		}
		cout << "\n";
	}
	// Print the all common subsequence in longest length
	bool findLCS(string s1, string s2, bool visit[], int n1, int n2, int i, int j, int k, int length)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				this->printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				this->findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (this->findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || this->findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	void lcs(string s1, string s2)
	{
		// Get the size of string
		int n1 = s1.size();
		int n2 = s2.size();
		// First find the length of LCS
		int length = this->lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			bool visit[n1];
			for (int i = 0; i < length; ++i)
			{
				visit[i] = false;
			}
			// Print all longest common subsequence of given two strings
			this->findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
};
int main()
{
	LongestSubsequence task = LongestSubsequence();
	string s1 = "XYZXYZXXZ";
	string s2 = "XZYXZYX";
	task.lcs(s1, s2);
	return 0;
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
// Include namespace system
using System;
/*
  C# Program for
  Print all 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 lcsLength(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 + lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return maxValue(lcsLength(s1, s2, n1, n2, i + 1, j), lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	public void printResult(String s, Boolean[] visit, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			if (visit[i] == true)
			{
				Console.Write(s[i]);
			}
		}
		Console.Write("\n");
	}
	// Print the all common subsequence in longest length
	public Boolean findLCS(String s1, String s2, Boolean[] visit, int n1, int n2, int i, int j, int k, int length)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	public void lcs(String s1, String s2)
	{
		// Get the size of string
		int n1 = s1.Length;
		int n2 = s2.Length;
		// First find the length of LCS
		int length = lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			Boolean[] visit = new Boolean[n1];
			for (int i = 0; i < length; ++i)
			{
				visit[i] = false;
			}
			// Print all longest common subsequence of given two strings
			findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
	public static void Main(String[] args)
	{
		LongestSubsequence task = new LongestSubsequence();
		String s1 = "XYZXYZXXZ";
		String s2 = "XZYXZYX";
		task.lcs(s1, s2);
	}
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
/*
  Node Js Program for
  Print all 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
	lcsLength(s1, s2, n1, n2, i, 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 + this.lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcsLength(s1, s2, n1, n2, i + 1, j), this.lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	printResult(s, visit, n)
	{
		for (var i = 0; i < n; ++i)
		{
			if (visit[i] == true)
			{
				process.stdout.write(s.charAt(i));
			}
		}
		process.stdout.write("\n");
	}
	// Print the all common subsequence in longest length
	findLCS(s1, s2, visit, n1, n2, i, j, k, length)
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1.charAt(i) == s2.charAt(j))
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				this.printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				this.findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (this.findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || this.findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	lcs(s1, s2)
	{
		// Get the size of string
		var n1 = s1.length;
		var n2 = s2.length;
		// First find the length of LCS
		var length = this.lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			var visit = Array(n1).fill(false);
			// Print all longest common subsequence of given two strings
			this.findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
}

function main()
{
	var task = new LongestSubsequence();
	var s1 = "XYZXYZXXZ";
	var s2 = "XZYXZYX";
	task.lcs(s1, s2);
}
main();

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
<?php
/*
  Php Program for
  Print all 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 lcsLength($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->lcsLength($s1, $s2, $n1, $n2, $i + 1, $j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return $this->maxValue($this->lcsLength($s1, $s2, $n1, $n2, $i + 1, $j),
                                   $this->lcsLength($s1, $s2, $n1, $n2, $i, $j + 1));
		}
	}
	// Display the result
	public	function printResult($s, & $visit, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			if ($visit[$i] == true)
			{
				echo $s[$i];
			}
		}
		echo "\n";
	}
	// Print the all common subsequence in longest length
	public	function findLCS($s1, $s2, & $visit, $n1, $n2, $i, $j, $k, $length)
	{
		if ($i == $n1 || $j == $n2)
		{
			// When string length exceeds
			return false;
		}
		else if ($s1[$i] == $s2[$j])
		{
			// When similar characters meet
			$visit[$i] = true;
			if ($k + 1 == $length)
			{
				$this->printResult($s1, $visit, $n1);
				$visit[$i] = false;
				return true;
			}
			else
			{
				$this->findLCS($s1, $s2, $visit, $n1, $n2, $i + 1, $j + 1, $k + 1, $length);
			}
			$visit[$i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if ($this->findLCS($s1, $s2, $visit, $n1, $n2, $i + 1, $j, $k, $length) 
                || $this->findLCS($s1, $s2, $visit, $n1, $n2, $i, $j + 1, $k, $length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	public	function lcs($s1, $s2)
	{
		// Get the size of string
		$n1 = strlen($s1);
		$n2 = strlen($s2);
		// First find the length of LCS
		$length = $this->lcsLength($s1, $s2, $n1, $n2, 0, 0);
		if ($length > 0)
		{
			$visit = array_fill(0, $n1, false);
			// Print all longest common subsequence of given two strings
			$this->findLCS($s1, $s2, $visit, $n1, $n2, 0, 0, 0, $length);
		}
	}
}

function main()
{
	$task = new LongestSubsequence();
	$s1 = "XYZXYZXXZ";
	$s2 = "XZYXZYX";
	$task->lcs($s1, $s2);
}
main();

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
#   Python 3 Program for
#   Print all 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 lcsLength(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.lcsLength(s1, s2, n1, n2, i + 1, j + 1)
		else :
			#  Through recursively find similar characters
			return self.maxValue(self.lcsLength(s1, s2, n1, n2, i + 1, j), self.lcsLength(s1, s2, n1, n2, i, j + 1))
		
	
	#  Display the result
	def printResult(self, s, visit, n) :
		i = 0
		while (i < n) :
			if (visit[i] == True) :
				print(s[i], end = "")
			
			i += 1
		
		print(end = "\n")
	
	#  Print the all common subsequence in longest length
	def findLCS(self, s1, s2, visit, n1, n2, i, j, k, length) :
		if (i == n1 or j == n2) :
			#  When string length exceeds
			return False
		
		elif(s1[i] == s2[j]) :
			#  When similar characters meet
			visit[i] = True
			if (k + 1 == length) :
				self.printResult(s1, visit, n1)
				visit[i] = False
				return True
			else :
				self.findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length)
			
			visit[i] = False
		else :
			#  Through recursively find similar characters
			if (self.findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) or self.findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length)) :
				return True
			
		
		return False
	
	#  Handles the request of display longest common subsequence
	def lcs(self, s1, s2) :
		#  Get the size of string
		n1 = len(s1)
		n2 = len(s2)
		#  First find the length of LCS
		length = self.lcsLength(s1, s2, n1, n2, 0, 0)
		if (length > 0) :
			visit = [False] * (n1)
			#  Print all longest common subsequence of given two strings
			self.findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length)
		
	

def main() :
	task = LongestSubsequence()
	s1 = "XYZXYZXXZ"
	s2 = "XZYXZYX"
	task.lcs(s1, s2)

if __name__ == "__main__": main()

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
#   Ruby Program for
#   Print all 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 lcsLength(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.lcsLength(s1, s2, n1, n2, i + 1, j + 1)
		else 
			#  Through recursively find similar characters
			return self.maxValue(self.lcsLength(s1, s2, n1, n2, i + 1, j), self.lcsLength(s1, s2, n1, n2, i, j + 1))
		end

	end

	#  Display the result
	def printResult(s, visit, n) 
		i = 0
		while (i < n) 
			if (visit[i] == true) 
				print(s[i])
			end

			i += 1
		end

		print("\n")
	end

	#  Print the all common subsequence in longest length
	def findLCS(s1, s2, visit, n1, n2, i, j, k, length) 
		if (i == n1 || j == n2) 
			#  When string length exceeds
			return false
		elsif(s1[i] == s2[j]) 
			#  When similar characters meet
			visit[i] = true
			if (k + 1 == length) 
				self.printResult(s1, visit, n1)
				visit[i] = false
				return true
			else 
				self.findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length)
			end

			visit[i] = false
		else 
			#  Through recursively find similar characters
			if (self.findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || self.findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length)) 
				return true
			end

		end

		return false
	end

	#  Handles the request of display longest common subsequence
	def lcs(s1, s2) 
		#  Get the size of string
		n1 = s1.length()
		n2 = s2.length()
		#  First find the length of LCS
		length = self.lcsLength(s1, s2, n1, n2, 0, 0)
		if (length > 0) 
			visit = Array.new(n1) {false}
			#  Print all longest common subsequence of given two strings
			self.findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length)
		end

	end

end

def main() 
	task = LongestSubsequence.new()
	s1 = "XYZXYZXXZ"
	s2 = "XZYXZYX"
	task.lcs(s1, s2)
end

main()

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX

/*
  Scala Program for
  Print all 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 lcsLength(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.lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcsLength(s1, s2, n1, n2, i + 1, j), this.lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	def printResult(s: String, visit: Array[Boolean], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			if (visit(i) == true)
			{
				print(s(i));
			}
			i += 1;
		}
		print("\n");
	}
	// Print the all common subsequence in longest length
	def findLCS(s1: String, s2: String, visit: Array[Boolean], n1: Int, n2: Int, i: Int, j: Int, k: Int, length: Int): Boolean = {
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1(i) == s2(j))
		{
			// When similar characters meet
			visit(i) = true;
			if (k + 1 == length)
			{
				this.printResult(s1, visit, n1);
				visit(i) = false;
				return true;
			}
			else
			{
				this.findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit(i) = false;
		}
		else
		{
			// Through recursively find similar characters
			if (this.findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) || this.findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	def lcs(s1: String, s2: String): Unit = {
		// Get the size of string
		var n1: Int = s1.length();
		var n2: Int = s2.length();
		// First find the length of LCS
		var length: Int = this.lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			var visit: Array[Boolean] = Array.fill[Boolean](n1)(false);
			// Print all longest common subsequence of given two strings
			this.findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LongestSubsequence = new LongestSubsequence();
		var s1: String = "XYZXYZXXZ";
		var s2: String = "XZYXZYX";
		task.lcs(s1, s2);
	}
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
/*
  Swift 4 Program for
  Print all 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 lcsLength(_ s1: [Character], _ s2: [Character], _ 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 + self.lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return self.maxValue(self.lcsLength(s1, s2, n1, n2, i + 1, j),
                                 self.lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	func printResult(_ s: [Character], _ visit: [Bool], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			if (visit[i] == true)
			{
				print(s[i], terminator: "");
			}
			i += 1;
		}
		print(terminator: "\n");
	}
	// Print the all common subsequence in longest length
	func findLCS(_ s1: [Character], _ s2: [Character], _ visit: inout[Bool], _ n1: Int, _ n2: Int, _ i: Int, _ j: Int, _ k: Int, _ length: Int)->Bool
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				self.printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				let _ = self.findLCS(s1, s2, &visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (self.findLCS(s1, s2, &visit, n1, n2, i + 1, j, k, length) 
                || self.findLCS(s1, s2, &visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	func lcs(_ str1: String, _ str2: String)
	{
      	let s1 = Array(str1);
      	let s2 = Array(str2);
		// Get the size 
		let n1: Int = s1.count;
		let n2: Int = s2.count;
      
		// First find the length of LCS
		let length: Int = self.lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			var visit: [Bool] = Array(repeating: false, count: n1);
			// Print all longest common subsequence of given two strings
			let _ = self.findLCS(s1, s2, &visit, n1, n2, 0, 0, 0, length);
		}
	}
}
func main()
{
	let task: LongestSubsequence = LongestSubsequence();
	let s1: String = "XYZXYZXXZ";
	let s2: String = "XZYXZYX";
	task.lcs(s1, s2);
}
main();

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
/*
  Kotlin Program for
  Print all 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 lcsLength(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.lcsLength(s1, s2, n1, n2, i + 1, j + 1);
		}
		else
		{
			// Through recursively find similar characters
			return this.maxValue(this.lcsLength(s1, s2, n1, n2, i + 1, j),
                                 this.lcsLength(s1, s2, n1, n2, i, j + 1));
		}
	}
	// Display the result
	fun printResult(s: String, visit: Array <Boolean> , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			if (visit[i] == true)
			{
				print(s[i]);
			}
			i += 1;
		}
		print("\n");
	}
	// Print the all common subsequence in longest length
	fun findLCS(s1: String, s2: String, visit: Array < Boolean > , n1: Int, n2: Int, i: Int, j: Int, k: Int, length: Int): Boolean
	{
		if (i == n1 || j == n2)
		{
			// When string length exceeds
			return false;
		}
		else if (s1[i] == s2[j])
		{
			// When similar characters meet
			visit[i] = true;
			if (k + 1 == length)
			{
				this.printResult(s1, visit, n1);
				visit[i] = false;
				return true;
			}
			else
			{
				this.findLCS(s1, s2, visit, n1, n2, i + 1, j + 1, k + 1, length);
			}
			visit[i] = false;
		}
		else
		{
			// Through recursively find similar characters
			if (this.findLCS(s1, s2, visit, n1, n2, i + 1, j, k, length) 
                || this.findLCS(s1, s2, visit, n1, n2, i, j + 1, k, length))
			{
				return true;
			}
		}
		return false;
	}
	// Handles the request of display longest common subsequence
	fun lcs(s1: String, s2: String): Unit
	{
		// Get the size of string
		var n1: Int = s1.count();
		var n2: Int = s2.count();
		// First find the length of LCS
		var length: Int = this.lcsLength(s1, s2, n1, n2, 0, 0);
		if (length > 0)
		{
			var visit: Array<Boolean> = Array(n1)
			{
				false
			};
			// Print all longest common subsequence of given two strings
			this.findLCS(s1, s2, visit, n1, n2, 0, 0, 0, length);
		}
	}
}
fun main(args: Array<String> ): Unit
{
	var task: LongestSubsequence = LongestSubsequence();
	var s1: String = "XYZXYZXXZ";
	var s2: String = "XZYXZYX";
	task.lcs(s1, s2);
}

Output

XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
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