Posted on by Kalkicode
Code Backtracking

# Print all longest common subsequence

In this article, we will discuss the problem of printing all the longest common subsequences between two given strings. We will provide an explanation of the problem statement, along with a suitable example. We will then present the pseudocode algorithm for solving the problem, along with a step-by-step explanation. Finally, we will analyze the resultant output and discuss the time complexity of the code.

## Problem Statement

The problem is to find and print all the longest common subsequences between two given strings. 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) is the subsequence that appears in both strings and has the maximum possible length.

## Example

Let's consider the following example:

```String 1: XYZXYZXXZ
String 2: XZYXZYX
```

The longest common subsequence between the two strings is "XZYXZ". However, there are multiple other subsequences that are also the longest with a length of 5: "XZYZX", "XZXZX", "XZXYX", "XYXZX", "XYXYX", and "XYZYX". The problem requires us to print all of these subsequences.

## Pseudocode Algorithm

Let's outline the pseudocode algorithm to solve this problem:

```function lcs_length(s1, s2):
if length of s1 is 0 or length of s2 is 0:
return 0
else if last character of s1 is the same as the last character of s2:
return 1 + lcs_length(s1[0:end-1], s2[0:end-1])
else:
return maximum of lcs_length(s1[0:end-1], s2) and lcs_length(s1, s2[0:end-1])

function print_result(s1, visit, n):
for i from 0 to n:
if visit[i] is 1:
print s1[i]
print newline

function find_lcs(s1, s2, visit, n1, n2, i, j, k, length):
if i is equal to n1 or j is equal to n2:
return 0
else if s1[i] is equal to s2[j]:
visit[i] = 1
if k + 1 is equal to 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:
if find_lcs(s1, s2, visit, n1, n2, i + 1, j, k, length) or find_lcs(s1, s2, visit, n1, n2, i, j + 1, k, length):
return 1
return 0

function lcs(s1, s2):
n1 = length of s1
n2 = length of s2
length = lcs_length(s1, s2, n1, n2, 0, 0)
if length > 0:
visit = array of size n1 initialized with 0
find_lcs(s1, s2, visit, n1, n2, 0, 0, 0, length)
```

## Code Solution

``````// 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)
{
String s1 = "XYZXYZXXZ";
String s2 = "XZYXZYX";
}
}``````

#### 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()
{
string s1 = "XYZXYZXXZ";
string s2 = "XZYXZYX";
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)
{
String s1 = "XYZXYZXXZ";
String s2 = "XZYXZYX";
}
}``````

#### 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 s1 = "XYZXYZXXZ";
var s2 = "XZYXZYX";
}
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()
{
\$s1 = "XYZXYZXXZ";
\$s2 = "XZYXZYX";
}
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() :
s1 = "XYZXYZXXZ"
s2 = "XZYXZYX"

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()
s1 = "XYZXYZXXZ"
s2 = "XZYXZYX"
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";
}
}``````

#### 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 s1: String = "XYZXYZXXZ";
let s2: String = "XZYXZYX";
}
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 s1: String = "XYZXYZXXZ";
var s2: String = "XZYXZYX";
}``````

#### Output

``````XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX``````

## Resultant Output

The code will output the following longest common subsequences between the given strings:

```XZYXZ
XZYZX
XZXZX
XZXYX
XYXZX
XYXYX
XYZYX
```

These are all the subsequences that have the maximum length of 5 and are common to both input strings.

## Time Complexity

The time complexity of this code is determined by the function `lcs_length`, which calculates the length of the longest common subsequence recursively. Let's denote the lengths of the input strings as `n` and `m`. The time complexity can be approximated as `O(2^(n+m))`, as there are two recursive calls for each character comparison, and the maximum depth of recursion is bounded by the sum of the lengths of the strings.

It's important to note that the actual time complexity may vary depending on the implementation and the specific inputs provided.

## 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.

Categories
Relative Post