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].
(screenshot, for a quicker reference)
- 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.
- 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.