# Longest Common Subsequence of three strings

**Longest Common Subsequence of three strings**: This is an extension of the normal longest common subsequence program for two strings.

Submitted by Radib Kar, on June 12, 2020

**Problem statement:**

Given 3 strings **X**, **Y** and **Z**, the task is to **find the longest common sub-sequence in all three given sequences**.

**Input:**

Given input is the length of three string **N**, **M**, **K** and then in the next lines the strings **X**, **Y**, **Z** themselves respectively

**Output:**

Print the length of the longest common sub- sequence of the three strings

**Constraints:**

1<= N, M, K <=100

**Example:**

Input:
N = 5, M = 6, K = 7
X = "inclu"
Y = "socluue"
Z = "anyclue"
Output:
The length of longest common subsequence for these three strings are 3

**Explanation:**

The longest common subsequence for these three strings is:

"clu" which is of length 3

We need a 3D table to store the computed values.

Let's say for sub-sequences,

Now if

X[i]==Y[j]==Z[k]then surely, we found a character which is common and we need to recur for the remaining onesIf they are not similar, we need to find maximum of three cases

X[i]recur for othersY[j]recur for othersZ[k]recur for othersSo, if we formulate the above idea in to our recursion function then

f(N-1,M,K)= LeaveX[i]recur for othersf(N,M-1,K)= LeaveY[j]recur for othersf(N,M,K-1)= LeaveZ[k]recur for othersNow, the above recursion will result to many overlapping sub problems. Hence, we need to convert the above to DP.

dp[M+1][N+1][K+1]Obviously, visual illustration for the 3D DP calculation is not possible, but you can go through the computation for LCS between two strings to understand how this 3D table is being filled.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: