Theorem 15.1 (Optimal Substructure of an LCS)

Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS.

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

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

  3. If $x_m \neq y_n$, then $z_k \neq y_n$ implies that Z is an LCS of X and $Y_{n-1}$.

format copied from related post

The above cases are intuitive and easily provable.

I do not understand additional cases not explicitly mentioned in the theorem:

What happens here:

$x_m \neq y_n$ and $z_k \neq x_m \neq y_n$

The above statement combines cases 2 and 3. Does that mean Z is an LCS of both LCS of $X_{m-1}$ and Y AND X and $Y_{n-1}$? That doesn't make sense to me.

  • 1
    $\begingroup$ You assume $x_m=y_n$ and then $z_k \ne x_m \ne y_n$. How is it possible $x_m=y_n$ and $x_m \ne y_n$? $\endgroup$ – fade2black Jan 16 at 23:08
  • $\begingroup$ ya just saw that, that is contradiction my bad $\endgroup$ – Anthony O Jan 16 at 23:09
  • $\begingroup$ What I am really interested in is combining cases 2 and 3. Z can be an LCS of π‘‹π‘šβˆ’1 and Y AND X and π‘Œπ‘›βˆ’1. Then we must consider both of these subproblems. $\endgroup$ – Anthony O Jan 16 at 23:10
  • $\begingroup$ $x_m \ne y_n$ and then $z_k \ne x_m \ne y_n$ is also repetition of assumption, $x_m\ \ne y_n$ two times? $\endgroup$ – fade2black Jan 16 at 23:12
  • 1
    $\begingroup$ You probably mean the case $x_m \ne y_n$ and $z_k \ne y_n$ and $z_k \ne x_m$. Then $Z$ is LCS of $X_{m-1}$ and $Y_{n-1}$. For example, X=(2,1,3,6,4) and Y=(4,2,8,3,6,5), and Z=(2,3,6). Here, $5 \ne 6$ and $4 \ne 6$.So Z is LCS of (2,1,3,6) and (4,2,8,3,6). But this case can be considered as one of the previous cases: second or third. $\endgroup$ – fade2black Jan 16 at 23:59

If $x_m = y_n$ then any longest common sequence must end with $x_m = y_n$. This is what the first item covers.

If $x_m \neq y_n$, then there are three types of longest common sequences:

  • Longest common sequences ending in $x_m$.
  • Longest common sequences ending in $y_n$.
  • Longest common sequences ending in neither.

These are all the cases. There is no other case.


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.