# Longest Common subsequence theorem in CLRS

In CLRS in the dynamic programming chapter, there is a theorem about the longest common subsequence prefix that states the following:

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 their LCS.

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}$$.

The theorem has two more points but I am interested particularly in the first point, I don't understand why we only consider $$Z_{k-1}$$ to be the LCS of $$X_{m−1}$$ and $$Y_{n−1}$$ and not $$Z$$ to be the LCS of all of $$X$$ and $$Y$$, if already the last element in all sequences match.

The theorem is used to construct a recurrence relation for computing the LCS of $$X$$ and $$Y$$. The first point states that if $$x_m = y_n$$, then one possible LCS of $$X$$ and $$Y$$ is an LCS of $$X_{m-1}$$ and $$Y_{n-1}$$ together with $$x_m$$. This is one of the cases in the recurrence relation.
You ask why we are not considering $$Z$$ as the LCS of $$X$$ and $$Y$$. There is no need to consider this, because this is already assumed to hold in the premise of the theorem. Given that, we want to deduce other information, which will later enable us to compute the LCS recursively.
• yes that's right, it's a recursive behavior, if $Z$ is LCS of $X \; \&\;Y$, and last elements are matching, then $Z_{k-1}$ must be LCS of $X_{m-1} \; \&\;Y_{n-1}$, ok now i got it, thanks a lot. May 24 '20 at 13:35