Skip to main content

Print Longest common subsequence

Here given code implementation process.

/*
    C program for
    Print Longest common subsequence
*/
#include <stdio.h>
#include <string.h>

int maxValue(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    return b;
}
void printLCP(char *text1, char *text2)
{
    // Get the length of text1 and text2
    int m = strlen(text1);
    int n = strlen(text2);

    int dp[m + 1][n + 1];
    // Execute loop through by size of m
    for (int i = 0; i <= m; i++)
    {
        // Execute loop through by size of n
        for (int j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
            {
                // Set first row and first column value is zero
                dp[i][j] = 0;
            }
            else if (text1[i - 1] == text2[j - 1])
            {
                // When i-1 and j-1 is character are same
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                // Get max value
                dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Find the length of longest common subsequence 
    int length = dp[m][n];
    // Use to collect result
    char result[length + 1];
    // Set terminate character at the end
    result[length] = '\0';

    int k = m;
    int l = n;
    while (k > 0 && l > 0)
    {
        if (text1[k - 1] == text2[l - 1])
        {
            length--;
            k--;
            l--;
            result[length] = text1[k];
     
        }
        else if (dp[k - 1][l] > dp[k][l - 1])
        {
            k--;
        }
        else
        {
            l--;
        }
    }
    printf("\n Given text1 : %s",text1);
    printf("\n Given text2 : %s",text2);
    // Display LCS
    printf("\n Result : %s", result);
}
int main(int argc, char const *argv[])
{
    char *text1 = "adsafbsasc";
    char *text2 = "hagvswebrca";
    printLCP(text1, text2);
    return 0;
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
/*
    Java program for
    Print Longest common subsequence
*/
public class LCP
{
    public int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        return b;
    }
    public void printLCP(String text1, String text2)
    {
        // Get the length of text1 and text2
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        // Execute loop through by size of m
        for (int i = 0; i <= m; i++)
        {
            // Execute loop through by size of n
            for (int j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0)
                {
                    // Set first row and first column value is zero
                    dp[i][j] = 0;
                }
                else if (text1.charAt(i - 1) == text2.charAt(j - 1))
                {
                    // When i-1 and j-1 is character are same
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    // Get max value
                    dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // Use to collect result
        String result = "";
        int k = m;
        int l = n;
        while (k > 0 && l > 0)
        {
            if (text1.charAt(k-1) == text2.charAt(l-1))
            {
                
                k--;
                l--;
                result = text1.charAt(k) + result;
            }
            else if (dp[k - 1][l] > dp[k][l - 1])
            {
                k--;
            }
            else
            {
                l--;
            }
        }
        System.out.print("\n Given text1 : " + text1);
        System.out.print("\n Given text2 : " + text2);
        // Display LCS
        System.out.print("\n Result : " + result);
    }
    public static void main(String[] args)
    {
        LCP task = new LCP();
        String text1 = "adsafbsasc";
        String text2 = "hagvswebrca";
        task.printLCP(text1, text2);
    }
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ program for
    Print Longest common subsequence
*/
class LCP
{
	public: int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	void printLCP(string text1, string text2)
	{
		// Get the length of text1 and text2
		int m = text1.length();
		int n = text2.length();
		int dp[m + 1][n + 1];
		// Execute loop through by size of m
		for (int i = 0; i <= m; i++)
		{
			// Execute loop through by size of n
			for (int j = 0; j <= n; j++)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp[i][j] = 0;
				}
				else if (text1[i - 1] == text2[j - 1])
				{
					// When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i][j] = this->maxValue(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		// Use to collect result
		string result = "";
		int k = m;
		int l = n;
		while (k > 0 && l > 0)
		{
			if (text1[k - 1] == text2[l - 1])
			{
				k--;
				l--;
				result = (text1[k])  +  result;
			}
			else if (dp[k - 1][l] > dp[k][l - 1])
			{
				k--;
			}
			else
			{
				l--;
			}
		}
		cout << "\n Given text1 : " << text1;
		cout << "\n Given text2 : " << text2;
		// Display LCS
		cout << "\n Result : " << result;
	}
};
int main()
{
	LCP *task = new LCP();
	string text1 = "adsafbsasc";
	string text2 = "hagvswebrca";
	task->printLCP(text1, text2);
	return 0;
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
// Include namespace system
using System;
/*
    Csharp program for
    Print Longest common subsequence
*/
public class LCP
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void printLCP(String text1, String text2)
	{
		// Get the length of text1 and text2
		int m = text1.Length;
		int n = text2.Length;
		int[,] dp = new int[m + 1,n + 1];
		// Execute loop through by size of m
		for (int i = 0; i <= m; i++)
		{
			// Execute loop through by size of n
			for (int j = 0; j <= n; j++)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp[i,j] = 0;
				}
				else if (text1[i - 1] == text2[j - 1])
				{
					// When i-1 and j-1 is character are same
					dp[i,j] = dp[i - 1,j - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i,j] = this.maxValue(dp[i - 1,j], dp[i,j - 1]);
				}
			}
		}
		// Use to collect result
		String result = "";
		int k = m;
		int l = n;
		while (k > 0 && l > 0)
		{
			if (text1[k - 1] == text2[l - 1])
			{
				k--;
				l--;
				result = text1[k] + result;
			}
			else if (dp[k - 1,l] > dp[k,l - 1])
			{
				k--;
			}
			else
			{
				l--;
			}
		}
		Console.Write("\n Given text1 : " + text1);
		Console.Write("\n Given text2 : " + text2);
		// Display LCS
		Console.Write("\n Result : " + result);
	}
	public static void Main(String[] args)
	{
		LCP task = new LCP();
		String text1 = "adsafbsasc";
		String text2 = "hagvswebrca";
		task.printLCP(text1, text2);
	}
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
package main
import "fmt"
/*
    Go program for
    Print Longest common subsequence
*/

func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func printLCP(text1, text2 string) {
	// Get the length of text1 and text2
	var m int = len(text1)
	var n int = len(text2)
	var dp = make([][]int,m+1)

	for i := 0; i<=m; i++ {
		dp[i] = make([]int,n+1)
	}
	// Execute loop through by size of m
	for i := 0 ; i <= m ; i++ {
		// Execute loop through by size of n
		for j := 0 ; j <= n ; j++ {
			if i == 0 || j == 0 {
				// Set first row and first column value is zero
				dp[i][j] = 0
			} else if text1[i - 1] == text2[j - 1] {
				// When i-1 and j-1 is character are same
				dp[i][j] = dp[i - 1][j - 1] + 1
			} else {
				// Get max value
				dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1])
			}
		}
	}
	// Use to collect result
	var result string = ""
	var k int = m
	var l int = n
	for (k > 0 && l > 0) {
		if text1[k - 1] == text2[l - 1] {
			k--
			l--
			result = string(text1[k]) + result
		} else if dp[k - 1][l] > dp[k][l - 1] {
			k--
		} else {
			l--
		}
	}
	fmt.Print("\n Given text1 : ", text1)
	fmt.Print("\n Given text2 : ", text2)
	// Display LCS
	fmt.Print("\n Result : ", result)
}
func main() {
	
	var text1 string = "adsafbsasc"
	var text2 string = "hagvswebrca"
	printLCP(text1, text2)
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
<?php
/*
    Php program for
    Print Longest common subsequence
*/
class LCP
{
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function printLCP($text1, $text2)
	{
		// Get the length of text1 and text2
		$m = strlen($text1);
		$n = strlen($text2);
		$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
		// Execute loop through by size of m
		for ($i = 0; $i <= $m; $i++)
		{
			// Execute loop through by size of n
			for ($j = 0; $j <= $n; $j++)
			{
				if ($i == 0 || $j == 0)
				{
					// Set first row and first column value is zero
					$dp[$i][$j] = 0;
				}
				else if ($text1[$i - 1] == $text2[$j - 1])
				{
					// When i-1 and j-1 is character are same
					$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
				}
				else
				{
					// Get max value
					$dp[$i][$j] = $this->maxValue($dp[$i - 1][$j], $dp[$i][$j - 1]);
				}
			}
		}
		// Use to collect result
		$result = "";
		$k = $m;
		$l = $n;
		while ($k > 0 && $l > 0)
		{
			if ($text1[$k - 1] == $text2[$l - 1])
			{
				$k--;
				$l--;
				$result = strval($text1[$k]).$result;
			}
			else if ($dp[$k - 1][$l] > $dp[$k][$l - 1])
			{
				$k--;
			}
			else
			{
				$l--;
			}
		}
		echo("\n Given text1 : ".$text1);
		echo("\n Given text2 : ".$text2);
		// Display LCS
		echo("\n Result : ".$result);
	}
}

function main()
{
	$task = new LCP();
	$text1 = "adsafbsasc";
	$text2 = "hagvswebrca";
	$task->printLCP($text1, $text2);
}
main();

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
/*
    Node JS program for
    Print Longest common subsequence
*/
class LCP
{
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	printLCP(text1, text2)
	{
		// Get the length of text1 and text2
		var m = text1.length;
		var n = text2.length;
		var dp = Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
		// Execute loop through by size of m
		for (var i = 0; i <= m; i++)
		{
			// Execute loop through by size of n
			for (var j = 0; j <= n; j++)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp[i][j] = 0;
				}
				else if (text1.charAt(i - 1) == text2.charAt(j - 1))
				{
					// When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i][j] = this.maxValue(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		// Use to collect result
		var result = "";
		var k = m;
		var l = n;
		while (k > 0 && l > 0)
		{
			if (text1.charAt(k - 1) == text2.charAt(l - 1))
			{
				k--;
				l--;
				result = text1.charAt(k) + result;
			}
			else if (dp[k - 1][l] > dp[k][l - 1])
			{
				k--;
			}
			else
			{
				l--;
			}
		}
		process.stdout.write("\n Given text1 : " + text1);
		process.stdout.write("\n Given text2 : " + text2);
		// Display LCS
		process.stdout.write("\n Result : " + result);
	}
}

function main()
{
	var task = new LCP();
	var text1 = "adsafbsasc";
	var text2 = "hagvswebrca";
	task.printLCP(text1, text2);
}
main();

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
#    Python 3 program for
#    Print Longest common subsequence
class LCP :
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def printLCP(self, text1, text2) :
		#  Get the length of text1 and text2
		m = len(text1)
		n = len(text2)
		dp = [[0] * (n + 1) for _ in range(m + 1) ]
		i = 0
		#  Execute loop through by size of m
		while (i <= m) :
			j = 0
			#  Execute loop through by size of n
			while (j <= n) :
				if (i == 0 or j == 0) :
					#  Set first row and first column value is zero
					dp[i][j] = 0
				elif (text1[i - 1] == text2[j - 1]) :
					#  When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1
				else :
					#  Get max value
					dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1])
				
				j += 1
			
			i += 1
		
		#  Use to collect result
		result = ""
		k = m
		l = n
		while (k > 0 and l > 0) :
			if (text1[k - 1] == text2[l - 1]) :
				k -= 1
				l -= 1
				result = str(text1[k]) + result
			elif (dp[k - 1][l] > dp[k][l - 1]) :
				k -= 1
			else :
				l -= 1
			
		
		print("\n Given text1 : ", text1, end = "")
		print("\n Given text2 : ", text2, end = "")
		#  Display LCS
		print("\n Result : ", result, end = "")
	

def main() :
	task = LCP()
	text1 = "adsafbsasc"
	text2 = "hagvswebrca"
	task.printLCP(text1, text2)

if __name__ == "__main__": main()

Output

 Given text1 :  adsafbsasc
 Given text2 :  hagvswebrca
 Result :  asbc
#    Ruby program for
#    Print Longest common subsequence
class LCP 
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def printLCP(text1, text2) 
		#  Get the length of text1 and text2
		m = text1.length
		n = text2.length
		dp = Array.new(m + 1) {Array.new(n + 1) {0}}
		i = 0
		#  Execute loop through by size of m
		while (i <= m) 
			j = 0
			#  Execute loop through by size of n
			while (j <= n) 
				if (i == 0 || j == 0) 
					#  Set first row and first column value is zero
					dp[i][j] = 0
				elsif (text1[i - 1] == text2[j - 1]) 
					#  When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1
				else
 
					#  Get max value
					dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1])
				end

				j += 1
			end

			i += 1
		end

		#  Use to collect result
		result = ""
		k = m
		l = n
		while (k > 0 && l > 0) 
			if (text1[k - 1] == text2[l - 1]) 
				k -= 1
				l -= 1
				result = text1[k].to_s + result
			elsif (dp[k - 1][l] > dp[k][l - 1]) 
				k -= 1
			else
 
				l -= 1
			end

		end

		print("\n Given text1 : ", text1)
		print("\n Given text2 : ", text2)
		#  Display LCS
		print("\n Result : ", result)
	end

end

def main() 
	task = LCP.new()
	text1 = "adsafbsasc"
	text2 = "hagvswebrca"
	task.printLCP(text1, text2)
end

main()

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
/*
    Scala program for
    Print Longest common subsequence
*/
class LCP()
{
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def printLCP(text1: String, text2: String): Unit = {
		// Get the length of text1 and text2
		var m: Int = text1.length();
		var n: Int = text2.length();
		var dp: Array[Array[Int]] = Array.fill[Int](m + 1, n + 1)(0);
		var i: Int = 0;
		// Execute loop through by size of m
		while (i <= m)
		{
			var j: Int = 0;
			// Execute loop through by size of n
			while (j <= n)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp(i)(j) = 0;
				}
				else if (text1.charAt(i - 1) == text2.charAt(j - 1))
				{
					// When i-1 and j-1 is character are same
					dp(i)(j) = dp(i - 1)(j - 1) + 1;
				}
				else
				{
					// Get max value
					dp(i)(j) = maxValue(dp(i - 1)(j), dp(i)(j - 1));
				}
				j += 1;
			}
			i += 1;
		}
		// Use to collect result
		var result: String = "";
		var k: Int = m;
		var l: Int = n;
		while (k > 0 && l > 0)
		{
			if (text1.charAt(k - 1) == text2.charAt(l - 1))
			{
				k -= 1;
				l -= 1;
				result = text1.charAt(k).toString() + result;
			}
			else if (dp(k - 1)(l) > dp(k)(l - 1))
			{
				k -= 1;
			}
			else
			{
				l -= 1;
			}
		}
		print("\n Given text1 : " + text1);
		print("\n Given text2 : " + text2);
		// Display LCS
		print("\n Result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LCP = new LCP();
		var text1: String = "adsafbsasc";
		var text2: String = "hagvswebrca";
		task.printLCP(text1, text2);
	}
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
import Foundation;
/*
    Swift 4 program for
    Print Longest common subsequence
*/
class LCP
{
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func printLCP(_ a: String, _ b: String)
	{
		// Get the length of text1 and text2
		let m: Int = a.count;
		let n: Int = b.count;
        let text1 = Array(a);
      	let text2 = Array(b);
		var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1);
		var i: Int = 0;
		// Execute loop through by size of m
		while (i <= m)
		{
			var j: Int = 0;
			// Execute loop through by size of n
			while (j <= n)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp[i][j] = 0;
				}
				else if (text1[i - 1] == text2[j - 1])
				{
					// When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1]);
				}
				j += 1;
			}
			i += 1;
		}
		// Use to collect result
		var result: String = "";
		var k: Int = m;
		var l: Int = n;
		while (k > 0 && l > 0)
		{
			if (text1[k - 1] == text2[l - 1])
			{
				k -= 1;
				l -= 1;
				result = String(text1[k]) + result;
			}
			else if (dp[k - 1][l] > dp[k][l - 1])
			{
				k -= 1;
			}
			else
			{
				l -= 1;
			}
		}
		print("\n Given text1 : ", a, terminator: "");
		print("\n Given text2 : ", b, terminator: "");
		// Display LCS
		print("\n Result : ", result, terminator: "");
	}
}
func main()
{
	let task: LCP = LCP();
	let text1: String = "adsafbsasc";
	let text2: String = "hagvswebrca";
	task.printLCP(text1, text2);
}
main();

Output

 Given text1 :  adsafbsasc
 Given text2 :  hagvswebrca
 Result :  asbc
/*
    Kotlin program for
    Print Longest common subsequence
*/
class LCP
{
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun printLCP(text1: String, text2: String): Unit
	{
		// Get the length of text1 and text2
		val m: Int = text1.length;
		val n: Int = text2.length;
		var dp: Array < Array < Int >> = Array(m + 1)
		{
			Array(n + 1)
			{
				0
			}
		};
		var i: Int = 0;
		// Execute loop through by size of m
		while (i <= m)
		{
			var j: Int = 0;
			// Execute loop through by size of n
			while (j <= n)
			{
				if (i == 0 || j == 0)
				{
					// Set first row and first column value is zero
					dp[i][j] = 0;
				}
				else if (text1.get(i - 1) == text2.get(j - 1))
				{
					// When i-1 and j-1 is character are same
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i][j] = this.maxValue(dp[i - 1][j], dp[i][j - 1]);
				}
				j += 1;
			}
			i += 1;
		}
		// Use to collect result
		var result: String = "";
		var k: Int = m;
		var l: Int = n;
		while (k > 0 && l > 0)
		{
			if (text1.get(k - 1) == text2.get(l - 1))
			{
				k -= 1;
				l -= 1;
				result = text1.get(k).toString() + result;
			}
			else if (dp[k - 1][l] > dp[k][l - 1])
			{
				k -= 1;
			}
			else
			{
				l -= 1;
			}
		}
		print("\n Given text1 : " + text1);
		print("\n Given text2 : " + text2);
		// Display LCS
		print("\n Result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: LCP = LCP();
	val text1: String = "adsafbsasc";
	val text2: String = "hagvswebrca";
	task.printLCP(text1, text2);
}

Output

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc
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