Longest Common Subsequence

Question

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$ ?

Answer 1

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$

Answer 2

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.

Coming to Your doubts:

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