1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.