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

Question

Рассмотрим 2 последовательности X [1..m] и Y [1..n]. Алгоритм запоминания будет вычислять LCS за время O (m * n). Есть ли лучший алгоритм, чтобы узнать LCS по времени? Я предполагаю, что памятка, сделанная по диагонали, может дать нам O (min (m, n)) сложность времени.

Answer 1

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

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

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

Answer 2

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

Answer 3

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