Ваша рекурсия восстонавливает ответ в динамическом программировании в матрице.
Построение матрицы менять не надо, оно просто считает оптимальную длину LCS. Вам надо отдавать приоритет переходам вверх (или влево) пока это возможно при восстановлении ответа.
Но можно сделать простой хак - усеките ваш текст как можно короче, пока LCS все еще оптимального размера.
Вам надо найти самое первое максимальное число в последней строке (или столбце, в зависимости от того в какой из входных строчек вы хотите как можно левее найти вхождение. Я не в курсе, что у вас за aCompareFunc).
От этой позиции и запускайте ваш DoDiff вместо левой нижней ячейки матрицы.
Значения максимума даже не надо искать, он будет в левом нижнем углу матрицы. Вам остается только циклом найти самое левое число в строке (столбце) равное последнему.
Вам еще придется в конце зарепортить необходимое количество l3diffDeleted или l3diffAdded, чтобы восстановить усеченную часть.
