Теоретический материал: наибольшая общая подпоследовательность

Наибольшая общая подпоследовательность (НОП, Longest Common Subsequence, LCS)

Условие

Рассмотрим последовательность чисел a₁, a₂, …, a_n. Если вычеркнуть из этой последовательности часть чисел, мы получим другую последовательность, которую называют подпоследовательностью данной последовательности.

Рассмотрим теперь еще одну последовательность b₁, b₂, …, b_m. Требуется найти длину самой длинной подпоследовательности последовательности {a_I}, которая одновременно является и подпоследовательностью последовательности {b_I}. Такую последовательность называют наибольшей общей подследовательностью (НОП). Например, для последовательностей 1, 2, 3, 4, 5 и 2, 7, 3, 2, 5 НОП является подпоследовательность 2, 3, 5, состоящая из трёх членов.

Решение

Будем решать эту задачу методом динамического программирования. Для этого опишем подзадачи, на которые мы будем разбивать нашу задачу. Мы напишем функцию LCS(p, q), которая находит длину НОП для двух начальных участков a₁, …, a_p и b₁, …, b_q наших последовательностей. Пусть для всех пар q и p (p < n, q < m), мы задачу решать уже научились.  Попробуем вычислить LCS(n, m). Рассмотрим два случая:

1)           a_n= b_m. Тогда LCS(n, m)=LCS(n-1, m-1)+1.

2)           a_n≠ b_m. Тогда LCS(n, m)=max(LCS(n, m-1), LCS(n-1, m)).

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

Данный алгоритм требует порядка O(nm) операций.