# Longest Common Subsequence

Let $X=<x_1,x_2,…,x_m>$ and $Y=<y_1,y_2,…,y_n>$ be sequences and let $Z=<z_1,z_2,…,z_k>$ a longest common subsequence (LCS) of $X$ and $Y$.Then:

1. If $x_m=y_n$,then $z_k=x_m=y_n$ and $Z_{k-1}$ is a LCS of $X_{m-1}$ and $Y_{n-1}$

2. If $x_m \neq y_n$ and $z_k \neq x_m$,it implies that $Z$ is a LCS of $X_{m-1}$ and $Y$

• I haven't understood why $x_m=y_n \Rightarrow z_k=x_m=y_n$. 

If we have for example $X=<A,B,E,A,F,A>$ and $Y=<D,F,B,A>$, should the last element of $Z$ be $A$,or can it also be $F$ or $B$ and we could write $A$ at which position we want?



• At the second sentence,why do we conclude that $Z$ is a LCS of $X_{m-1}$ and $Y$ ?

CS stands for common subseseuqnce and LCS stands for longest common subsequence

Firstly, by definition, we call $b_k = a_{n_k}, k=1,2,\cdots$ a subsequence of $(a_n)_{n=1,2,\cdots}$ if $n_k$ is strictly increasing as a function of $k$.

Using your example, if $X = <A,B,E,A,F,A>$, then $<A,E,F,A>$ is its subequence but $<F,E,B>$ is not. Although all the three elements(F, E and B) are contained in $X$, they don't appear in the right order.

Then we have $X=<x_1,x_2,…,x_m>$, $Y=<y_1,y_2,…,y_n>$ and $Z=<z_1,z_2,…,z_k>$ is a LCS of X and Y. We prove if $x_m =y_n$ then $z_k = x_m=y_n$ by contradiction.

Suppose $z_k \neq x_m$, then we can construct another CS of $X$ and $Y$ by adding $x_m$(i.e.$y_n$) at the end of $Z$, but the new CS is longer than $Z$, which is contradictory with the fact that $Z$ is a LCS. Thus we have proven if $x_m =y_n$ then $z_k = x_m=y_n$

Now since $z_k=x_m=y_n$, obviously $Z_{k-1}$ is a CS of $X_{m-1}$ and $Y_{n-1}$. If $X_{m-1}$ and $Y_{n-1}$ has a CS longer than $Z_{k-1}$, then by adding $z_k$ at the end of this new CS, we get a CS of $X$ and $Y$, which is longer than $Z$. Contradiction

Next, we will prove $x_m \neq y_n$ and $z_k \neq x_m$ implies that $Z$ is a LCS of $X_{m-1}$ and $Y$.

Since $z_k \neq x_m$, $Z$ is a subsequence of $X_{m-1}=<x_1,x_2,\cdots,x_{m-1}>$, thus it is a CS of $X_{m-1}$ and $Y$. It is the longest one because if there is another one longer than it, then this longer one will also be CS of $X$ and $Y$, thus in contradiction with the fact that $Z$ is a LCS of $X$ and $Y$. So $Z$ has to be a LCS of $X_{m-1}$ and $Y$

• I have edited my post..Could you take a look? :) Aug 12, 2014 at 13:45
• @evinda I think we are using the same definition. Aug 12, 2014 at 17:41
• @evinda I added more details. Aug 16, 2014 at 22:11
• Liu Gang I understood it know!!!thank you very much!!! :) Aug 16, 2014 at 22:33
• You are welcome:) Aug 16, 2014 at 22:34

Just to make things clear

Common Sub Sequence:A sub sequence is a sequence that appears in both Sequences in the same relative order but not necessarily contiguous.

And the longest common sub sequence refers to finding the longest of all css.

For the example mentioned

X=A B E A F A

Y=D F B A

The LCS will be < B A > or < F A >. And please remember that you should not change the order of the Sequence elements ==> A should be only at the last.

1.If x[m] = y[n] Then realize that if you find the lcs of X< x[1] ... x[m-1] > and Y< y[1] ....y[n-1]> and append x[m] (or y[n]) to it , you have the lcs of X< x1 ...... xm> and Y< y1 ...ym>

You can observe that in your example. Since the last character is same in both sequences ==> Your task is simplified to find the lcs of X<1..m-1> and Y<1..n-1> and append this last character to the lcs found ==> Z[1...k] = < Z[1..k-1] , A>

==> z[k] = A

2.If x[m] ≠ y[n] and z[k] ≠ x[m],it implies that Z is a LCS of X[1...m−1] and Y[1..n]

Since z[k] ≠ x[m] && x[m] ≠ y[n] , You are sure that x[m] is not a part of LCS .Then your problem reduces to finding the LCS of X[1..m-1] and Y[1..n] , LCS of X[1..m] and Y[1..n-1] and making z[k] the maximum of the two.

Please comment if my explanation is not clear. A good tutorial can be found here

• Could you explain me the following:  Then your problem reduces to finding the LCS of X[1..m-1] and Y[1..n] , LCS of X[1..m] and Y[1..n-1] and making z[k] the maximum of the two.  Why do we have to find the LCS of $X[1 \dots m]$ and $Y[1 \dots n-1]$,knowing that $x[m] \neq z[k]$ ? Aug 16, 2014 at 23:45
• Are you trying to get an algorithm for finding the LCS of two sequences or checking whether a given Sequence is LCS of two sequences ? Aug 17, 2014 at 0:41
• No,I just wanted to understand the sentences.. Aug 17, 2014 at 21:56