8.5. Задача LCS

Наибольшая общая подпоследовательность из двух последовательностейНаибольшая общая подпоследовательность из двух последовательностей

Мы имеем две последовательности и , их общая подпоследовательность длиной — это набор индексов

при котором

Наибольшая общая подпоследовательность — общая подпоследовательность, которая обладает наибольшей длиной из всех подпоследовательностей.

Такая задача может применяться, например:
— в сопоставлении данных — утилита diff, операция слияния в разных системах управления версиями;
— в биоинформатике — поиск сходств в генах разных видов;
— в проверке орфографии.

• Входные данные: Первая строка: количество элементов первой подпоследовательности . Вторая строка: . Третья строка: количество элементов второй подпоследовательности . Четвёртая строка: .
• Выходные данные: .
• Ограничения: ; для всех .

Пример 1Пример 1

Ввод	Вывод
3 2 7 5 2 2 5	2

• Общая подпоследовательность длиной 2 — это .

Пример 2Пример 2

Ввод	Вывод
1 7 4 1 2 3 4	0

• У двух последовательностей нет общих элементов.

Пример 3Пример 3

Ввод	Вывод
4 2 7 8 3 4 5 2 8 7	2

• Одна общая подпоследовательность — . Ещё одна — .

РешениеРешение

Рассмотрим наибольшую общую подпоследовательность , определённую индексами и (так, для каждого , ):
— Последние символы и приводятся в . В этом случае и . Тогда — это наибольшая общая подпоследовательность от и .
— Как минимум один из последних символов и не приводится в . В этом случае или , или . Тогда находится полностью в или .

Таким образом, мы сводим задачу с изначальными строками и до такой же задачи с их префиксами. Пусть — длина наибольшей общей подпоследовательности и . Выходит, что эта функция удовлетворяет следующее рекуррентное соотношение:

Базовый случай для этого рекуррентного соотношения — или :

Полученный алгоритм приведён ниже. Его время выполнения составляет .

LCS(A[1…n],B[1…m]):
    table = 2d array of size (n+1)×(m+1)
    table[i][0] = 0 and table[0][j] = 0 for all i,j
    for i from 1 to n:
        for j from 1 to m:
            table[i][j] = table[i−1][j]
            table[i][j] = max(table[i][j], table[i][j−1])
            if A[i]=B[j]:
                table[i][j] = max(table[i][j], table[i−1][j−1]+1)
    return table[n][m]

💡 Остановитесь и подумайте:
Получится ли у вас свести задачу «Наибольшая общая подпоследовательность» до задачи «Редакционное расстояние»?

Подсказка: Наибольшая общая подпоследовательность и получается путём удаления определённых символов из и .

Так задача «Наибольшая общая подпоследовательность» — всего лишь задача «Редакционное расстояние», в которой запрещены операции «замены».

Наибольшая общая подпоследовательность из трёх последовательностейНаибольшая общая подпоследовательность из трёх последовательностей

Имея три последовательности: , и — нужно найти длину наибольшей общей подпоследовательности для них, то есть наибольшее неотрицательное целое число , при котором существуют индексы

при котором

• Входные данные: Первая строка: . Вторая строка: . Третья строка: . Четвёртая строка: . Пятая строка: . Шестая строка: .
• Выходные данные: .
• Ограничения: ; .

Пример 1Пример 1

Ввод	Вывод
3 1 2 3 3 2 1 3 3 1 3 5	2

Пример 2Пример 2

Ввод	Вывод
5 8 3 2 1 7 7 8 2 1 3 8 10 7 6 6 8 3 1 4 7	3

• В этом случае одна общая подпоследовательность длиной 3 — это . Ещё одна — .

РешениеРешение

Пусть — это максимальная длина общей подпоследовательности от , и .

Тогда

Базовый случай:

Время выполнения соответствующего алгоритма составляет .