Posted on by Kalkicode
Code Dynamic Programming

Longest common subsequence of three sequences

In this article, we will discuss the problem of finding the longest common subsequence (LCS) of three sequences. We will explain the problem statement, provide a pseudocode algorithm with an explanation, and discuss the resultant output. The time complexity of the code will also be analyzed.

Problem Statement

The problem is to find the longest common subsequence among three given sequences. A subsequence is a sequence that can be derived by deleting some or no elements from the original sequence without changing the order of the remaining elements. The task is to find the length of the longest common subsequence that is present in all three sequences.

Pseudocode Algorithm

Let's walk through the pseudocode algorithm for finding the longest common subsequence of three sequences:

function maxValue(a, b):
    if a > b:
        return a
    else:
        return b

function lengthOfLCP(text1, text2, text3):
    m = length(text1)
    n = length(text2)
    o = length(text3)
    dp[m][n][o]

    for i from 0 to m:
        for j from 0 to n:
            for k from 0 to o:
                if i = 0 or j = 0 or k = 0:
                    dp[i][j][k] = 1
                else if text1[i-1] = text2[j-1] and text2[j-1] = text3[k-1]:
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                else:
                    dp[i][j][k] = maxValue(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

    print "Given text1: " + text1
    print "Given text2: " + text2
    print "Given text3: " + text3
    print "Result: " + dp[m-1][n-1][o-1]

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

The algorithm uses dynamic programming to solve the problem. It creates a three-dimensional array, dp, to store the lengths of the common subsequences. The algorithm iterates through the lengths of the three sequences and compares the characters at each position. If the characters are equal, it adds 1 to the length of the previous common subsequence. Otherwise, it takes the maximum length from the three adjacent positions in the dp array.

Code Solution

/*
    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

Resultant Output

When the given sequences are "pdfpofindther", "pminoiwinters", and "codepokingtenter", the output will be:

Given text1: pdfpofindther
Given text2: pminoiwinters
Given text3: codepokingtenter
Result: 7

The output indicates that the longest common subsequence among the three sequences has a length of 7.

Time Complexity

The time complexity of the algorithm is determined by the nested loops that iterate through the lengths of the three sequences. Let m, n, and o be the lengths of the three sequences, respectively.

The algorithm has a time complexity of O(m * n * o) because each element in the three-dimensional dp array is calculated once in constant time. Therefore, the algorithm's time complexity is directly proportional to the product of the lengths of the three sequences.

As a result, the algorithm efficiently finds the longest common subsequence among three sequences using dynamic programming.

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