Skip to main content

Longest common subsequence of three sequences

Here given code implementation process.

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

int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
void lengthOfLCP(char *text1, char *text2, char *text3)
{
	// Get the length of text1 and text2
	int m = strlen(text1);
	int n = strlen(text2);
	int o = strlen(text3);
	int dp[m][n][o];
	// Execute loop through by size of text1
	for (int i = 0; i < m; ++i)
	{
		// Execute loop through by size of text2
		for (int j = 0; j < n; ++j)
		{
			// Execute loop through by size of text3
			for (int k = 0; k < o; ++k)
			{
				if (i == 0 || j == 0 || k == 0)
				{
					dp[i][j][k] = 1;
				}
				else if (text1[i - 1] == text2[j - 1] && 
                         text2[j - 1] == text3[k - 1])
				{
					// When i-1 and j-1 and k-1 is character are same
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
				}
				else
				{
					// Get max value
					dp[i][j][k] = maxValue(
                      maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                      dp[i][j][k - 1]);
				}
			}
		}
	}
	// Given string
	printf("\n Given text1 : %s", text1);
	printf("\n Given text2 : %s", text2);
	printf("\n Given text3 : %s", text3);
	// Display length of LCS
	printf("\n Result : %d", dp[m - 1][n - 1][o - 1]);
}
int main(int argc, char
	const *argv[])
{
	char *text1 = "pdfpofindther";
	char *text2 = "pminoiwinters";
	char *text3 = "codepokingtenter";
	// "pointer" Common sequences
	// Result : 7
	lengthOfLCP(text1, text2, text3);
	return 0;
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
/*
    Java program for
    Longest common subsequence of three sequences
*/
public class LCP
{
    public int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        return b;
    }
    public void lengthOfLCP(String text1, String text2, String text3)
    {
        // Get the length of text1 and text2
        int m = text1.length();
        int n = text2.length();
        int o = text3.length();
        int[][][] dp = new int[m][n][o];
        // Execute loop through by size of text1
        for (int i = 0; i < m; ++i)
        {
            // Execute loop through by size of text2
            for (int j = 0; j < n; ++j)
            {
                // Execute loop through by size of text3
                for (int k = 0; k < o; ++k)
                {
                    if (i == 0 || j == 0 || k == 0)
                    {
                        dp[i][j][k] = 1;
                    }
                    else if (text1.charAt(i - 1) == text2.charAt(j - 1) && 
                             text2.charAt(j - 1) == text3.charAt(k - 1))
                    {
                        // When i-1 and j-1 and k-1 is character are same
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                    }
                    else
                    {
                        // Get max value
                        dp[i][j][k] = maxValue(
                          maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1]);
                    }
                }
            }
        }
        // Given string
        System.out.print("\n Given text1 : " + text1);
        System.out.print("\n Given text2 : " + text2);
        System.out.print("\n Given text3 : " + text3);
        // Display length of LCS
        System.out.print("\n Result : " + dp[m - 1][n - 1][o - 1] );
    }
    public static void main(String[] args)
    {
        LCP task = new LCP();
        String text1 = "pdfpofindther";
        String text2 = "pminoiwinters";
        String text3 = "codepokingtenter";
        task.lengthOfLCP(text1, text2,text3);
    }
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ program for
    Longest common subsequence of three sequences
*/
class LCP
{
	public: int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	void lengthOfLCP(string text1, string text2, string text3)
	{
		// Get the length of text1 and text2
		int m = text1.length();
		int n = text2.length();
		int o = text3.length();
		int dp[m][n][o];
		// Execute loop through by size of text1
		for (int i = 0; i < m; ++i)
		{
			// Execute loop through by size of text2
			for (int j = 0; j < n; ++j)
			{
				// Execute loop through by size of text3
				for (int k = 0; k < o; ++k)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp[i][j][k] = 1;
					}
					else if (text1[i - 1] == text2[j - 1] && 
                             text2[j - 1] == text3[k - 1])
					{
						// When i-1 and j-1 and k-1 is character are same
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					}
					else
					{
						// Get max value
						dp[i][j][k] = this->maxValue(
                          this->maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1]);
					}
				}
			}
		}
		// Given string
		cout << "\n Given text1 : " << text1;
		cout << "\n Given text2 : " << text2;
		cout << "\n Given text3 : " << text3;
		// Display length of LCS
		cout << "\n Result : " << dp[m - 1][n - 1][o - 1];
	}
};
int main()
{
	LCP *task = new LCP();
	string text1 = "pdfpofindther";
	string text2 = "pminoiwinters";
	string text3 = "codepokingtenter";
	task->lengthOfLCP(text1, text2, text3);
	return 0;
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
// Include namespace system
using System;
/*
    Csharp program for
    Longest common subsequence of three sequences
*/
public class LCP
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void lengthOfLCP(String text1, String text2, String text3)
	{
		// Get the length of text1 and text2
		int m = text1.Length;
		int n = text2.Length;
		int o = text3.Length;
		int[,,] dp = new int[m,n,o];
		// Execute loop through by size of text1
		for (int i = 0; i < m; ++i)
		{
			// Execute loop through by size of text2
			for (int j = 0; j < n; ++j)
			{
				// Execute loop through by size of text3
				for (int k = 0; k < o; ++k)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp[i,j,k] = 1;
					}
					else if (text1[i - 1] == text2[j - 1] && 
                             text2[j - 1] == text3[k - 1])
					{
						// When i-1 and j-1 and k-1 is character are same
						dp[i,j,k] = dp[i - 1,j - 1,k - 1] + 1;
					}
					else
					{
						// Get max value
						dp[i,j,k] = this.maxValue(
                          this.maxValue(dp[i - 1,j,k], dp[i,j - 1,k]), 
                          dp[i,j,k - 1]);
					}
				}
			}
		}
		// Given string
		Console.Write("\n Given text1 : " + text1);
		Console.Write("\n Given text2 : " + text2);
		Console.Write("\n Given text3 : " + text3);
		// Display length of LCS
		Console.Write("\n Result : " + dp[m - 1,n - 1,o - 1]);
	}
	public static void Main(String[] args)
	{
		LCP task = new LCP();
		String text1 = "pdfpofindther";
		String text2 = "pminoiwinters";
		String text3 = "codepokingtenter";
		task.lengthOfLCP(text1, text2, text3);
	}
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
package main
import "fmt"
/*
    Go program for
    Longest common subsequence of three sequences
*/

func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func lengthOfLCP(text1, text2, text3 string) {
	// Get the length of text1 and text2
	var m int = len(text1)
	var n int = len(text2)
	var o int = len(text3)
	var dp = make([][][]int,m);
	for i := 0 ; i < m ; i++ {
		dp[i] = make([][]int,n)
		for j := 0 ; j < n ; j++ {
			dp[i][j] = make([]int,o)
		}
	}

	// Execute loop through by size of text1
	for i := 0 ; i < m ; i++ {
		// Execute loop through by size of text2
		for j := 0 ; j < n ; j++ {
			// Execute loop through by size of text3
			for k := 0 ; k < o ; k++ {
				if i == 0 || j == 0 || k == 0 {
					dp[i][j][k] = 1
				} else if text1[i - 1] == text2[j - 1] && text2[j - 1] == text3[k - 1] {
					// When i-1 and j-1 and k-1 is character are same
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
				} else {
					// Get max value
					dp[i][j][k] = maxValue(maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1])
				}
			}
		}
	}
	// Given string
	fmt.Print("\n Given text1 : ", text1)
	fmt.Print("\n Given text2 : ", text2)
	fmt.Print("\n Given text3 : ", text3)
	// Display length of LCS
	fmt.Print("\n Result : ", dp[m - 1][n - 1][o - 1])
}
func main() {

	var text1 string = "pdfpofindther"
	var text2 string = "pminoiwinters"
	var text3 string = "codepokingtenter"
	lengthOfLCP(text1, text2, text3)
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
<?php
/*
    Php program for
    Longest common subsequence of three sequences
*/
class LCP
{
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function lengthOfLCP($text1, $text2, $text3)
	{
		// Get the length of text1 and text2
		$m = strlen($text1);
		$n = strlen($text2);
		$o = strlen($text3);
		$dp = array_fill(0, $m, array_fill(0, $n, array_fill(0, $o, 0)));
		// Execute loop through by size of text1
		for ($i = 0; $i < $m; ++$i)
		{
			// Execute loop through by size of text2
			for ($j = 0; $j < $n; ++$j)
			{
				// Execute loop through by size of text3
				for ($k = 0; $k < $o; ++$k)
				{
					if ($i == 0 || $j == 0 || $k == 0)
					{
						$dp[$i][$j][$k] = 1;
					}
					else if ($text1[$i - 1] == $text2[$j - 1] && 
                             $text2[$j - 1] == $text3[$k - 1])
					{
						// When i-1 and j-1 and k-1 is character are same
						$dp[$i][$j][$k] = $dp[$i - 1][$j - 1][$k - 1] + 1;
					}
					else
					{
						// Get max value
						$dp[$i][$j][$k] = $this->maxValue(
                       		$this->maxValue($dp[$i - 1][$j][$k], 
                                       $dp[$i][$j - 1][$k]), 
                          $dp[$i][$j][$k - 1]);
					}
				}
			}
		}
		// Given string
		echo("\n Given text1 : ".$text1);
		echo("\n Given text2 : ".$text2);
		echo("\n Given text3 : ".$text3);
		// Display length of LCS
		echo("\n Result : ".$dp[$m - 1][$n - 1][$o - 1]);
	}
}

function main()
{
	$task = new LCP();
	$text1 = "pdfpofindther";
	$text2 = "pminoiwinters";
	$text3 = "codepokingtenter";
	$task->lengthOfLCP($text1, $text2, $text3);
}
main();

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
/*
    Node JS program for
    Longest common subsequence of three sequences
*/
class LCP
{
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	lengthOfLCP(text1, text2, text3)
	{
		// Get the length of text1 and text2
		var m = text1.length;
		var n = text2.length;
		var o = text3.length;
		var dp = 
            Array(m).fill(0).map(() => new Array(n).fill(0).map(
              () => new Array(o).fill(0)));
		// Execute loop through by size of text1
		for (var i = 0; i < m; ++i)
		{
			// Execute loop through by size of text2
			for (var j = 0; j < n; ++j)
			{
				// Execute loop through by size of text3
				for (var k = 0; k < o; ++k)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp[i][j][k] = 1;
					}
					else if (text1.charAt(i - 1) == text2.charAt(j - 1) && 
                             text2.charAt(j - 1) == text3.charAt(k - 1))
					{
						// When i-1 and j-1 and k-1 is character are same
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					}
					else
					{
						// Get max value
						dp[i][j][k] = this.maxValue(
                          this.maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1]);
					}
				}
			}
		}
		// Given string
		process.stdout.write("\n Given text1 : " + text1);
		process.stdout.write("\n Given text2 : " + text2);
		process.stdout.write("\n Given text3 : " + text3);
		// Display length of LCS
		process.stdout.write("\n Result : " + dp[m - 1][n - 1][o - 1]);
	}
}

function main()
{
	var task = new LCP();
	var text1 = "pdfpofindther";
	var text2 = "pminoiwinters";
	var text3 = "codepokingtenter";
	task.lengthOfLCP(text1, text2, text3);
}
main();

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
#    Python 3 program for
#    Longest common subsequence of three sequences
class LCP :
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def lengthOfLCP(self, text1, text2, text3) :
		#  Get the length of text1 and text2
		m = len(text1)
		n = len(text2)
		o = len(text3)
		dp = [[[0] * (o) for _ in range(n) ]
		for _ in range(m) ]
		i = 0
		#  Execute loop through by size of text1
		while (i < m) :
			j = 0
			#  Execute loop through by size of text2
			while (j < n) :
				k = 0
				#  Execute loop through by size of text3
				while (k < o) :
					if (i == 0 or j == 0 or k == 0) :
						dp[i][j][k] = 1
					elif (text1[i - 1] == text2[j - 1] and 
                          text2[j - 1] == text3[k - 1]) :
						#  When i-1 and j-1 and k-1 is character are same
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
					else :
						#  Get max value
						dp[i][j][k] = self.maxValue(
                          self.maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1])
					
					k += 1
				
				j += 1
			
			i += 1
		
		#  Given string
		print("\n Given text1 : ", text1, end = "")
		print("\n Given text2 : ", text2, end = "")
		print("\n Given text3 : ", text3, end = "")
		#  Display length of LCS
		print("\n Result : ", dp[m - 1][n - 1][o - 1], end = "")
	

def main() :
	task = LCP()
	text1 = "pdfpofindther"
	text2 = "pminoiwinters"
	text3 = "codepokingtenter"
	task.lengthOfLCP(text1, text2, text3)

if __name__ == "__main__": main()

Output

 Given text1 :  pdfpofindther
 Given text2 :  pminoiwinters
 Given text3 :  codepokingtenter
 Result :  7
#    Ruby program for
#    Longest common subsequence of three sequences
class LCP 
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

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

					k += 1
				end

				j += 1
			end

			i += 1
		end

		#  Given string
		print("\n Given text1 : ", text1)
		print("\n Given text2 : ", text2)
		print("\n Given text3 : ", text3)
		#  Display length of LCS
		print("\n Result : ", dp[m - 1][n - 1][o - 1])
	end

end

def main() 
	task = LCP.new()
	text1 = "pdfpofindther"
	text2 = "pminoiwinters"
	text3 = "codepokingtenter"
	task.lengthOfLCP(text1, text2, text3)
end

main()

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
/*
    Scala program for
    Longest common subsequence of three sequences
*/
class LCP()
{
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def lengthOfLCP(text1: String, text2: String, text3: String): Unit = {
		// Get the length of text1 and text2
		var m: Int = text1.length();
		var n: Int = text2.length();
		var o: Int = text3.length();
		var dp: Array[Array[Array[Int]]] = Array.fill[Int](m, n, o)(0);
		var i: Int = 0;
		// Execute loop through by size of text1
		while (i < m)
		{
			var j: Int = 0;
			// Execute loop through by size of text2
			while (j < n)
			{
				var k: Int = 0;
				// Execute loop through by size of text3
				while (k < o)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp(i)(j)(k) = 1;
					}
					else if (text1.charAt(i - 1) == text2.charAt(j - 1) && 
                             text2.charAt(j - 1) == text3.charAt(k - 1))
					{
						// When i-1 and j-1 and k-1 is character are same
						dp(i)(j)(k) = dp(i - 1)(j - 1)(k - 1) + 1;
					}
					else
					{
						// Get max value
						dp(i)(j)(k) = maxValue(
                          maxValue(dp(i - 1)(j)(k), dp(i)(j - 1)(k)), 
                          dp(i)(j)(k - 1));
					}
					k += 1;
				}
				j += 1;
			}
			i += 1;
		}
		// Given string
		print("\n Given text1 : " + text1);
		print("\n Given text2 : " + text2);
		print("\n Given text3 : " + text3);
		// Display length of LCS
		print("\n Result : " + dp(m - 1)(n - 1)(o - 1));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LCP = new LCP();
		var text1: String = "pdfpofindther";
		var text2: String = "pminoiwinters";
		var text3: String = "codepokingtenter";
		task.lengthOfLCP(text1, text2, text3);
	}
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
import Foundation;
/*
    Swift 4 program for
    Longest common subsequence of three sequences
*/
class LCP
{
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func lengthOfLCP(_ a: String, _ b: String, _ c: String)
	{
		// Get the length of text1 and text2
		let m: Int = a.count;
		let n: Int = b.count;
		let o: Int = c.count;
      	let text1 = Array(a);
        let text2 = Array(b);
        let text3 = Array(c);
      
		var dp: [[[Int]]] = Array(
          repeating: Array(
          		repeating: Array(repeating: 0, count: o), count: n), count: m);
		var i: Int = 0;
		// Execute loop through by size of text1
		while (i < m)
		{
			var j: Int = 0;
			// Execute loop through by size of text2
			while (j < n)
			{
				var k: Int = 0;
				// Execute loop through by size of text3
				while (k < o)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp[i][j][k] = 1;
					}
					else if (text1[i - 1] == text2[j - 1] && 
                             text2[j - 1] == text3[k - 1])
					{
						// When i-1 and j-1 and k-1 is character are same
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					}
					else
					{
						// Get max value
						dp[i][j][k] = self.maxValue(
                          self.maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1]);
					}
					k += 1;
				}
				j += 1;
			}
			i += 1;
		}
		// Given string
		print("\n Given text1 : ", a, terminator: "");
		print("\n Given text2 : ", b, terminator: "");
		print("\n Given text3 : ", c, terminator: "");
		// Display length of LCS
		print("\n Result : ", dp[m - 1][n - 1][o - 1], terminator: "");
	}
}
func main()
{
	let task: LCP = LCP();
	let text1: String = "pdfpofindther";
	let text2: String = "pminoiwinters";
	let text3: String = "codepokingtenter";
	task.lengthOfLCP(text1, text2, text3);
}
main();

Output

 Given text1 :  pdfpofindther
 Given text2 :  pminoiwinters
 Given text3 :  codepokingtenter
 Result :  7
/*
    Kotlin program for
    Longest common subsequence of three sequences
*/
class LCP
{
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun lengthOfLCP(text1: String, text2: String, text3: String): Unit
	{
		// Get the length of text1 and text2
		val m: Int = text1.length;
		val n: Int = text2.length;
		val o: Int = text3.length;
		var dp: Array < Array < Array < Int >>> = Array(m)
		{
			Array(n)
			{
				Array(o)
				{
					0
				}
			}
		};
		var i: Int = 0;
		// Execute loop through by size of text1
		while (i < m)
		{
			var j: Int = 0;
			// Execute loop through by size of text2
			while (j < n)
			{
				var k: Int = 0;
				// Execute loop through by size of text3
				while (k < o)
				{
					if (i == 0 || j == 0 || k == 0)
					{
						dp[i][j][k] = 1;
					}
					else if (text1.get(i - 1) == text2.get(j - 1) && 
                             text2.get(j - 1) == text3.get(k - 1))
					{
						// When i-1 and j-1 and k-1 is character are same
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					}
					else
					{
						// Get max value
						dp[i][j][k] = this.maxValue(
                          this.maxValue(dp[i - 1][j][k], dp[i][j - 1][k]), 
                          dp[i][j][k - 1]);
					}
					k += 1;
				}
				j += 1;
			}
			i += 1;
		}
		// Given string
		print("\n Given text1 : " + text1);
		print("\n Given text2 : " + text2);
		print("\n Given text3 : " + text3);
		// Display length of LCS
		print("\n Result : " + dp[m - 1][n - 1][o - 1]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: LCP = LCP();
	val text1: String = "pdfpofindther";
	val text2: String = "pminoiwinters";
	val text3: String = "codepokingtenter";
	task.lengthOfLCP(text1, text2, text3);
}

Output

 Given text1 : pdfpofindther
 Given text2 : pminoiwinters
 Given text3 : codepokingtenter
 Result : 7
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