Самая длинная общая подпоследовательность

Question

Рассмотрим 2 последовательности x [1..m] и y [1..n]. Алгоритм метезаизации вычисляет LC во времена O (M * N). Есть ли лучший алгоритм, чтобы узнать LCS Wrt Time? Я думаю, что мемузаризация, сделанная по диагонали может дать нам (мин (M, N)) сложность времени.

Answer 1

Gene Myers в 1986 году придумал очень хороший алгоритм для этого, описанный здесь: Алгоритм разности O (ND) и его вариации.

Этот алгоритм требует времени пропорционально расстоянию редактирования между последовательностями, поэтому он намного быстрее, когда разница немана. Он работает путем обработки всех возможных редактирования расстояний, начиная с 0, до тех пор, пока он не найдет расстояние, для которого можно построить скрипт редактирования (в некотором смысле двойника LC). Это означает, что вы можете «выручить рано», если разница растет выше некоторого порога, что иногда удобно.

Я верю, что этот алгоритм все еще используется во многих diff Реализации.

Answer 2

Если вы знаете априорную верхнюю границу на максимальном размере k. Вы заботитесь о том, вы можете заставить алгоритм LCS выйти рано, добавив дополнительную проверку во внутренней петле. Это означает, что тогда, когда k << min (m, n) Вы можете получить небольшое время работы, несмотря на то, что вы делаете ЛК.

Answer 3

Да, мы могли бы создать лучший алгоритм, чем заказ o (m * n) --- то есть o (min (m, n)). Чтобы найти длину ..... просто сравнивайте диагональные элементы. И всякий раз, когда приращение сделано, предположим, что это произошло в C [2,2], затем увеличивайте все значение от C [2,2 ++] и C [2+ +, 2] на 1 .. и продолжить до C [м, м] .. (Предположим, м