Why does the LCS algorithm find a match at the end of a sequence?

Question

Algorithms

If I have two sequences "ABC" and "ABCABCABC", then my implementation of the LCS algorithm finds a match in the last part of the longer string, not the first. Is this a general property of this algorithm, or have I implemented something incorrectly?

Damn, I don't have the knowledge to ask the right question. :(

I implemented the algorithm a few years ago, I just rewrote it from some other implementation. In any case, I will be glad if someone tells me something.

Answer 1

Your recursion reconstructs the answer in dynamic programming in the matrix.
The construction of the matrix does not need to be changed, it simply considers the optimal LCS length. You should prioritize up (or left) transitions as long as possible when restoring the response.
But a simple hack can be done - truncate your text as short as possible while the LCS is still the optimal size.
You need to find the very first maximum number in the last row (or column, depending on which of the input lines you want to find the entry as far to the left as possible. I don't know what your aCompareFunc is).
From this position and run your DoDiff instead of the bottom left cell of the matrix.
You don’t even need to look for the maximum values, it will be in the lower left corner of the matrix. You just have to loop to find the leftmost number in the row (column) equal to the last one.
You still have to report the required number of l3diffDeleted or l3diffAdded at the end to recover the truncated part.