Print Longest common subsequence

In this article, we will discuss the problem of finding and printing the Longest Common Subsequence (LCS) between two given strings. The Longest Common Subsequence is the longest sequence of characters that appears in the same order in both strings.

Problem Statement

The problem is as follows: given two strings, we want to find the longest subsequence that is common to both strings and print it.

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. For example, consider the strings "ABCD" and "ACDF". The longest common subsequence between them is "ACD".

Pseudocode Algorithm

Let's understand the algorithm to solve this problem:

printLCP(text1, text2):
	// Get the length of text1 and text2
	m = length(text1)
	n = length(text2)

	// Create a 2D array to store the dynamic programming values
	dp[m+1][n+1]

	// Initialize the first row and first column with zeros
	for i = 0 to m:
		dp[i][0] = 0
	for j = 0 to n:
		dp[0][j] = 0

	// Fill the dynamic programming table
	for i = 1 to m:
		for j = 1 to n:
			if text1[i-1] == text2[j-1]:
				dp[i][j] = dp[i-1][j-1] + 1
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	// Find the length of the LCS
	length = dp[m][n]

	// Create a character array to store the LCS
	result[length+1]

	// Trace back to find the LCS
	k = m
	l = n
	while k > 0 and 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--

	// Print the given texts and the result
	print "Given text1:", text1
	print "Given text2:", text2
	print "Result:", result

Explanation

Let's go through the explanation of the code and the resulting output step by step:

1. The given texts are "adsafbsasc" and "hagvswebrca".
2. The algorithm uses dynamic programming to find the LCS between the texts.
3. A 2D array, dp, is initialized to store the dynamic programming values. The size of the array is determined by the lengths of the texts.
4. The algorithm iterates through the characters of the texts and fills the dp array according to the LCS logic.
5. After filling the dp array, the length of the LCS is obtained from dp[m][n].
6. A character array, result, is created to store the LCS.
7. Using the dp array, the algorithm traces back and constructs the LCS character by character.
8. The resulting LCS is stored in the result array.
9. Finally, the given texts and the resulting LCS are printed.

Resultant Output Explanation

The given texts are:

Given text1: adsafbsasc
Given text2: hagvswebrca

The longest common subsequence (LCS) between the given texts is:

Result: asbc

Code Solution

• C
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

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

 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);
    }
}

 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;
}

 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);
	}
}

 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)
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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);
}

 Given text1 : adsafbsasc
 Given text2 : hagvswebrca
 Result : asbc

Time Complexity

The time complexity of this algorithm is O(m * n), where m and n are the lengths of the input texts. This is because we iterate through the entire dp array of size (m+1) * (n+1).