8.5. Задача LCS

В этом параграфе вы разберёте задачу поиска наибольшей общей подпоследовательности (LCS) двух или трёх последовательностей. Такие задачи встречаются в системах контроля версий, биоинформатике и при сравнении текстов. Вы узнаете, как построить динамическое решение, которое работает значительно быстрее перебора, и как аккуратно реализовать алгоритм для двух и трёх строк.

Ключевые вопросы параграфа

• Что такое наибольшая общая подпоследовательность и как её находить?
• Почему простой перебор работает медленно и как ускорить решение с помощью динамического программирования?
• Как устроен алгоритм LCS для двух и трёх последовательностей и как реализовать его эффективно?

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

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

при котором

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

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

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

Пример 1

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

Пример 2

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

Пример 3

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

Решение

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

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

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

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

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

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

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

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

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

при котором

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

Пример 1

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

Пример 2

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

Решение

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

Тогда

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

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

Что дальше

Теперь вы умеете находить наибольшую общую подпоследовательность двух или трёх строк с помощью алгоритма динамического программирования. Вы увидели, как рекурсивные зависимости помогают выразить решение через подзадачи, и научились реализовывать алгоритм так, чтобы он был быстрым и устойчивым на практике.

Далее — задача о рюкзаке. Вы узнаете, как использовать похожие техники динамики, чтобы выбирать оптимальное подмножество предметов с максимальной суммарной ценностью при ограниченном объёме.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• LCS — это задача поиска самой длинной общей подпоследовательности двух или трёх строк.

• Полный перебор всех подпоследовательностей даёт экспоненциальную сложность, но динамическое программирование решает задачу за или .

• Решение строится на сравнении последних символов и рекурсивном переходе к префиксам строк.

• Алгоритм можно реализовать итеративно с таблицей и дополнительно восстановить саму подпоследовательность.