Tutorialspoint.dev

LCS (Longest Common Subsequence) of three strings

Given 3 strings of all having length < 100,the task is to find the longest common sub-sequence in all three given sequences.

Examples:

Input : str1 = "geeks"  
        str2 = "geeksfor"  
        str3 = "geeksforgeeks"
Output : 5
Longest common subsequence is "geeks"
i.e., length = 5

Input : str1 = "abcd1e2"  
        str2 = "bc12ea"  
        str3 = "bd1ea"
Output : 3
Longest common subsequence is "b1e" 
i.e. length = 3.


This problem is simply an extension of LCS

Let the input sequences be X[0..m-1], Y[0..n-1] and Z[0..o-1] of lengths m, n and o respectively. And let L(X[0..m-1], Y[0..n-1], Z[0..o-1]) be the lengths of LCS of the three sequences X, Y and Z. Following is the implementation:



The idea is to take a 3D array to store the 
length of common subsequence in all 3 given 
sequences i. e., L[m + 1][n + 1][o + 1]

1- If any of the string is empty then there
   is no common subsequence at all then
           L[i][j][k] = 0

2- If the characters of all sequences match
   (or X[i] == Y[j] ==Z[k]) then
        L[i][j][k] = 1 + L[i-1][j-1][k-1]

3- If the characters of both sequences do 
   not match (or X[i] != Y[j] || X[i] != Z[k] 
   || Y[j] !=Z[k]) then
        L[i][j][k] = max(L[i-1][j][k], 
                         L[i][j-1][k], 
                         L[i][j][k-1])

Below is implementation of above idea.

C++

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;
  
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
   and Z[0..o-1] */
int lcsOf3( string X, string Y, string Z, int m,
                               int n, int o)
{
    int L[m+1][n+1][o+1];
  
    /* Following steps build L[m+1][n+1][o+1] in
       bottom up fashion. Note that L[i][j][k]
       contains length of LCS of X[0..i-1] and
       Y[0..j-1]  and Z[0.....k-1]*/
    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            for (int k=0; k<=o; k++)
            {
                if (i == 0 || j == 0||k==0)
                    L[i][j][k] = 0;
  
                else if (X[i-1] == Y[j-1] && X[i-1]==Z[k-1])
                    L[i][j][k] = L[i-1][j-1][k-1] + 1;
  
                else
                    L[i][j][k] = max(max(L[i-1][j][k],
                                         L[i][j-1][k]),
                                     L[i][j][k-1]);
            }
        }
    }
  
    /* L[m][n][o] contains length of LCS for
      X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
    return L[m][n][o];
}
  
/* Driver program to test above function */
int main()
{
    string X = "AGGT12";
    string Y = "12TXAYB";
    string Z = "12XBA";
  
    int m = X.length();
    int n = Y.length();
    int o = Z.length();
  
    cout << "Length of LCS is " << lcsOf3(X, Y,
                                    Z, m, n, o);
  
    return 0;
}

Java

// Java program to find LCS of three strings
public class LCS_3Strings {
       
    /* Returns length of LCS for X[0..m-1], Y[0..n-1]
       and Z[0..o-1] */
    static int lcsOf3(String X, String Y, String Z, int m,
                                   int n, int o)
    {
        int[][][] L = new int[m+1][n+1][o+1];
       
        /* Following steps build L[m+1][n+1][o+1] in
           bottom up fashion. Note that L[i][j][k]
           contains length of LCS of X[0..i-1] and
           Y[0..j-1]  and Z[0.....k-1]*/
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                for (int k=0; k<=o; k++)
                {
                    if (i == 0 || j == 0||k==0)
                        L[i][j][k] = 0;
       
                    else if (X.charAt(i - 1) == Y.charAt(j - 1
                                && X.charAt(i - 1)==Z.charAt(k - 1))
                        L[i][j][k] = L[i-1][j-1][k-1] + 1;
       
                    else
                        L[i][j][k] = Math.max(Math.max(L[i-1][j][k],
                                             L[i][j-1][k]),
                                         L[i][j][k-1]);
                }
            }
        }
       
        /* L[m][n][o] contains length of LCS for
          X[0..n-1] and Y[0..m-1] and Z[0..o-1]*/
        return L[m][n][o];
    }
       
    /* Driver program to test above function */
    public static void main(String args[])
    {
        String X = "AGGT12";
        String Y = "12TXAYB";
        String Z = "12XBA";
       
        int m = X.length();
        int n = Y.length();
        int o = Z.length();
       
        System.out.println("Length of LCS is " +
                                lcsOf3(X, Y,Z, m, n, o));
       
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to find
# LCS of three strings
  
# Returns length of LCS
# for X[0..m-1], Y[0..n-1]
# and Z[0..o-1]
def lcsOf3(X, Y, Z, m, n, o):
      
    L = [[[0 for i in range(o+1)] for j in range(n+1)]
         for k in range(m+1)]
  
    ''' Following steps build L[m+1][n+1][o+1] in
    bottom up fashion. Note that L[i][j][k]
    contains length of LCS of X[0..i-1] and
    Y[0..j-1] and Z[0.....k-1] '''
    for i in range(m+1):
        for j in range(n+1):
            for k in range(o+1):
                if (i == 0 or j == 0 or k == 0):
                    L[i][j][k] = 0
                      
                elif (X[i-1] == Y[j-1] and
                      X[i-1] == Z[k-1]):
                    L[i][j][k] = L[i-1][j-1][k-1] + 1
  
                else:
                    L[i][j][k] = max(max(L[i-1][j][k],
                    L[i][j-1][k]),
                                    L[i][j][k-1])
  
    # L[m][n][o] contains length of LCS for
    # X[0..n-1] and Y[0..m-1] and Z[0..o-1]
    return L[m][n][o]
  
# Driver program to test above function
  
X = 'AGGT12'
Y = '12TXAYB'
Z = '12XBA'
  
m = len(X)
n = len(Y)
o = len(Z)
  
print('Length of LCS is', lcsOf3(X, Y, Z, m, n, o))
  
# This code is contributed by Soumen Ghosh.                    

C#

// C# program to find 
// LCS of three strings
using System;
  
class GFG 
{
      
    /* Returns length of LCS 
    for X[0..m-1], Y[0..n-1]
    and Z[0..o-1] */
    static int lcsOf3(String X, String Y, 
                      String Z, int m,
                      int n, int o)
    {
        int [,,]L = new int[m + 1, 
                            n + 1, o + 1];
      
        /* Following steps build 
        L[m+1][n+1][o+1] in bottom 
        up fashion. Note that 
        L[i][j][k] contains length 
        of LCS of X[0..i-1] and
        Y[0..j-1] and Z[0.....k-1]*/
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                for (int k = 0; k <= o; k++)
                {
                    if (i == 0 || 
                        j == 0 || k == 0)
                        L[i, j, k] = 0;
      
                    else if (X[i - 1] == Y[j - 1] && 
                             X[i - 1] == Z[k - 1])
                        L[i, j, k] = L[i - 1, 
                                       j - 1,
                                       k - 1] + 1;
      
                    else
                        L[i, j, k] = Math.Max(Math.Max(L[i - 1, j, k], 
                                                       L[i, j - 1, k]),
                                                       L[i, j, k - 1]);
                }
            }
        }
      
        /* L[m][n][o] contains length 
        of LCS for X[0..n-1] and
        Y[0..m-1] and Z[0..o-1]*/
        return L[m, n, o];
    }
      
    // Driver Code
    public static void Main()
    {
        string X = "AGGT12";
        string Y = "12TXAYB";
        string Z = "12XBA";
      
        int m = X.Length;
        int n = Y.Length;
        int o = Z.Length;
      
        Console.Write("Length of LCS is "
                       lcsOf3(X, Y, Z, m, n, o));
    }
}
  
// This code is contributed 
// by shiv_bhakt.

PHP

<?php 
// PHP program to find 
// LCS of three strings
  
/* Returns length of LCS for
X[0..m-1], Y[0..n-1] and Z[0..o-1] */
function lcsOf3($X, $Y, $Z
                $m, $n, $o)
{
    $L[$m + 1][$n + 1][$o + 1] = array(array(array()));
  
    /* Following steps build 
    L[m+1][n+1][o+1] in bottom 
    up fashion. Note that 
    L[i][j][k] contains length
    of LCS of X[0..i-1] and
    Y[0..j-1] and Z[0.....k-1]*/
    for ($i = 0; $i <= $m; $i++)
    {
        for ($j = 0; $j <= $n; $j++)
        {
            for ($k = 0; $k <= $o; $k++)
            {
                if ($i == 0 || $j == 0||$k == 0)
                    $L[$i][$j][$k] = 0;
  
                else if ($X[$i - 1] == $Y[$j - 1] && 
                         $X[$i - 1] == $Z[$k - 1])
                    $L[$i][$j][$k] = $L[$i - 1][$j - 1][$k - 1] + 1;
  
                else
                    $L[$i][$j][$k] = max(max($L[$i - 1][$j][$k],
                                              $L[$i][$j - 1][$k]),
                                             $L[$i][$j][$k - 1]);
            }
        }
    }
  
    /* L[m][n][o] contains length 
    of LCS for X[0..n-1] and 
    Y[0..m-1] and Z[0..o-1]*/
    return $L[$m][$n][$o];
}
  
// Driver code
$X = "AGGT12";
$Y = "12TXAYB";
$Z = "12XBA";
  
$m = strlen($X);
$n = strlen($Y);
$o = strlen($Z);
  
echo "Length of LCS is "
      lcsOf3($X, $Y, $Z
             $m, $n, $o);
  
// This code is contributed
// by ChitraNayal
?>


Output:

Length of LCS is 2

Another approach: (Using recursion)

C++

// C++ program to find LCS of three strings
#include<bits/stdc++.h>
using namespace std;
  
    string X = "AGGT12"
    string Y = "12TXAYB"
    string Z = "12XBA"
  
int dp[100][100][100];
  
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
int lcsOf3(int i, int j,int k)
{
    if(i==-1||j==-1||k==-1)
        return 0;
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];
      
    if(X[i]==Y[j] && Y[j]==Z[k])
        return dp[i][j][k] = 1+lcsOf3(i-1,j-1,k-1);
    else
        return dp[i][j][k] = max(max(lcsOf3(i-1,j,k),
                            lcsOf3(i,j-1,k)),lcsOf3(i,j,k-1));
}
  
// Driver code
int main()
{
    memset(dp, -1,sizeof(dp));
    int m = X.length(); 
    int n = Y.length(); 
    int o = Z.length(); 
  
    cout << "Length of LCS is " << lcsOf3(m-1,n-1,o-1);
// this code is contributed by Kushdeep Mittal
}

Java

// Java program to find LCS of three strings 
class GFG 
{
  
    static String X = "AGGT12";
    static String Y = "12TXAYB";
    static String Z = "12XBA";
  
    static int[][][] dp = new int[100][100][100];
  
    /* Returns length of LCS for X[0..m-1], 
    Y[0..n-1] and Z[0..o-1] */
    static int lcsOf3(int i, int j, int k) 
    {
        if (i == -1 || j == -1 || k == -1)
        {
            return 0;
        }
        if (dp[i][j][k] != -1
        {
            return dp[i][j][k];
        }
  
        if (X.charAt(i) == Y.charAt(j) &&
            Y.charAt(j) == Z.charAt(k))
        {
            return dp[i][j][k] = 1 + lcsOf3(i - 1, j - 1, k - 1);
        } else {
            return dp[i][j][k] = Math.max(Math.max(lcsOf3(i - 1, j, k),
                                lcsOf3(i, j - 1, k)),
                                lcsOf3(i, j, k - 1));
        }
    }
  
    // Driver code 
    public static void main(String[] args)
    {
  
        for (int i = 0; i < 100; i++)
        {
            for (int j = 0; j < 100; j++) 
            {
                for (int k = 0; k < 100; k++) 
                {
                    dp[i][j][k] = -1;
                }
            }
        }
        int m = X.length();
        int n = Y.length();
        int o = Z.length();
  
        System.out.print("Length of LCS is "
                + lcsOf3(m - 1, n - 1, o - 1));
    }
}
  
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to find LCS of
# three strings 
X = "AGGT12"
Y = "12TXAYB"
Z = "12XBA"
  
dp = [[[-1 for i in range(100)] 
           for j in range(100)] 
           for k in range(100)] 
          
# Returns length of LCS for 
# X[0..m-1], Y[0..n-1] and Z[0..o-1]
def lcsOf3(i, j, k) :
  
    if(i == -1 or j == -1 or k == -1) :
        return 0
          
    if(dp[i][j][k] != -1) :
        return dp[i][j][k]
      
    if(X[i] == Y[j] and Y[j] == Z[k]) :
        dp[i][j][k] = 1 + lcsOf3(i - 1
                                 j - 1, k - 1
        return dp[i][j][k]
          
    else :
        dp[i][j][k] = max(max(lcsOf3(i - 1, j, k), 
                              lcsOf3(i, j - 1, k)), 
                              lcsOf3(i, j, k - 1))
          
        return dp[i][j][k]
  
# Driver code 
if __name__ == "__main__"
    m = len(X)
    n = len(Y) 
    o = len(Z) 
  
    print("Length of LCS is"
           lcsOf3(m - 1, n - 1, o - 1))
      
# This code is contributed by Ryuga

C#

// C# program to find LCS of three strings 
using System; 
  
class GFG 
static string X = "AGGT12"
static string Y = "12TXAYB"
static string Z = "12XBA"
  
static int[,,] dp = new int[100, 100, 100]; 
  
/* Returns length of LCS for X[0..m-1], 
Y[0..n-1] and Z[0..o-1] */
static int lcsOf3(int i, int j, int k) 
    if(i == -1 || j == -1 || k == -1) 
        return 0; 
    if(dp[i, j, k] != -1) 
        return dp[i, j, k]; 
      
    if(X[i] == Y[j] && Y[j] == Z[k]) 
        return dp[i, j, k] = 1 + lcsOf3(i - 1, j - 1, k - 1); 
    else
        return dp[i, j, k] = Math.Max(Math.Max(lcsOf3(i - 1, j, k), 
                                               lcsOf3(i, j - 1, k)),
                                               lcsOf3(i, j, k - 1)); 
  
// Driver code 
static void Main() 
    for(int i = 0; i < 100; i++)
        for(int j = 0; j < 100; j++)
            for(int k = 0; k < 100; k++)
                dp[i, j, k] = -1;
    int m = X.Length; 
    int n = Y.Length; 
    int o = Z.Length; 
  
    Console.Write("Length of LCS is "
                   lcsOf3(m - 1, n - 1, o - 1)); 
}
}
  
// This code is contributed by DrRoot_

PHP

<?php
// PHP program to find LCS of three strings
  
    $X = "AGGT12"
    $Y = "12TXAYB"
    $Z = "12XBA"
  
    $dp=array_fill(0, 100, array_fill(0, 100, array_fill(0, 100, -1)));
  
/* Returns length of LCS for X[0..m-1], Y[0..n-1]
and Z[0..o-1] */
function lcsOf3($i, $j, $k)
{
    global $dp, $X, $Y, $Z;
    if($i == -1 || $j == -1 || $k == -1)
        return 0;
    if($dp[$i][$j][$k] != -1)
        return $dp[$i][$j][$k];
      
    if($X[$i] == $Y[$j] && $Y[$j] == $Z[$k])
        return $dp[$i][$j][$k] = 1+lcsOf3($i - 1, $j - 1, $k - 1);
    else
        return $dp[$i][$j][$k] = max(max(lcsOf3($i - 1, $j, $k),
                            lcsOf3($i, $j - 1, $k)), lcsOf3($i, $j, $k - 1));
}
  
// Driver code
    $m = strlen($X); 
    $n = strlen($Y); 
    $o = strlen($Z); 
  
    echo "Length of LCS is ".lcsOf3($m - 1, $n - 1, $o - 1);
  
// This code is contributed by mits
  
?>

Output:

Length of LCS is 2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter