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, 2021 at 23:08
  • $\begingroup$ ya just saw that, that is contradiction my bad $\endgroup$
    – Anthony O
    Jan 16, 2021 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, 2021 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, 2021 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, 2021 at 23:59

1 Answer 1

Reset to default
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 and acknowledge you have read our privacy policy.

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