1
$\begingroup$

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-calculated, if you go up a tad bit. C[i][j] stores the LCSLength for given str1[1...i], str2[1...j].

enter image description here (screenshot, for a quicker reference)

  1. My understanding is that it generates all the common sequences since either or both if conditions at the end are satisfied, which runs the program for the sub-cases. Once the last letters are matched, every string upto that point (with the current X[i] as the last letter) is printed.

I somewhere fail to digest the algorithm properly and completely. An explanation might help me very much.

  1. In the penultimate if, does changing writing the piece of code as R := R $\cup$ backtrackAll(C, X, Y, i, j-1) (instead of R := backtrackAll(C, X, Y, i, j-1)) change anything? I feel that it doesn't, given it's a top down approach and it only unions with the empty set R = {} above. Note that R is already defined above and the if is reached only after going through that empty set definition step, which rules out the possibility of having an error output.
$\endgroup$
  • $\begingroup$ Have you tried programming the algorithm and checking some of your suspicions? $\endgroup$ – Yuval Filmus Oct 10 at 12:39
  • $\begingroup$ I see the exact same code already available here and it only prints the LCS and not all the CS strings, which means my understanding (as in the first bullet) seems invalid. I still don't know why. $\endgroup$ – oldsailorpopoye Oct 10 at 15:37
  • $\begingroup$ @YuvalFilmus Could you please give me a reason/hint for this? $\endgroup$ – oldsailorpopoye Oct 14 at 20:58
  • $\begingroup$ The answer to your second question is: it makes no difference. $\endgroup$ – Yuval Filmus Oct 14 at 21:23
1
$\begingroup$

Wikipedia is being sloppy. The procedure returns all LCSs of $X[1..i]$ and $Y[1..j]$, which corresponds to $C[i,j]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.

If $X[i] = Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ is obtained by taking an LCS of $X[1..i-1]$ and $Y[1..j-1]$, and adding to it $X[i] = Y[j]$.

If $X[i] \neq Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ must be either an LCS of $X[1..i-1]$ and $Y[1..j]$, or an LCS of $X[1..i]$ and $Y[1..j-1]$ (or both). If $C[i-1,j] > C[i,j-1]$, then only the former are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] < C[i,j-1]$, then only the latter are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] = C[i,j-1]$, then both types are LCSs of $X[1..i]$ and $Y[1..j]$.

This recursive procedure could count the same sequence more than once — this happens for example for the arrays $ab$ and $ac$, where $a$ will be reached twice.

| cite | 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.