1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ aha, so in the theorem premise it is assumed that Z is a LCS, so we don't need to prove that, we only want to deal with the prefix cases to build the recurrence relation ? $\endgroup$ – markeb May 24 at 13:30
  • $\begingroup$ 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. $\endgroup$ – markeb May 24 at 13:35

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.