# How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?

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.

• 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$? – fade2black Jan 16 at 23:08
• ya just saw that, that is contradiction my bad – Anthony O Jan 16 at 23:09
• 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. – Anthony O Jan 16 at 23:10
• $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? – fade2black Jan 16 at 23:12
• 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. – 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$$.