Почему LCS алгоритм находит совпадение в конце последовательности?

Если у меня есть две последовательности «ABC» и «ABCABCABC», то моя реализация LCS-алгоритма находит совпадение в последней части более длинной строки, а не в первой. Это общее свойство этого алгоритма или у меня что-то неправильно реализовано?

Проклятье, у меня не хватает знаний, чтобы верно задать вопрос. :(

Алгоритм реализовал несколько лет назад, просто переписал из какой-то чужой реализации. В любом случае, буду рад, если кто-нибудь что-нибудь подскажет.
  • Вопрос задан
  • 68 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Ваша рекурсия восстонавливает ответ в динамическом программировании в матрице.

Построение матрицы менять не надо, оно просто считает оптимальную длину LCS. Вам надо отдавать приоритет переходам вверх (или влево) пока это возможно при восстановлении ответа.

Но можно сделать простой хак - усеките ваш текст как можно короче, пока LCS все еще оптимального размера.

Вам надо найти самое первое максимальное число в последней строке (или столбце, в зависимости от того в какой из входных строчек вы хотите как можно левее найти вхождение. Я не в курсе, что у вас за aCompareFunc).

От этой позиции и запускайте ваш DoDiff вместо левой нижней ячейки матрицы.

Значения максимума даже не надо искать, он будет в левом нижнем углу матрицы. Вам остается только циклом найти самое левое число в строке (столбце) равное последнему.

Вам еще придется в конце зарепортить необходимое количество l3diffDeleted или l3diffAdded, чтобы восстановить усеченную часть.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы