EssayAI
Блог
Блог
Естественные науки

Наибольшая общая подпоследовательность: алгоритм и пример

8 ноября 2026Время чтения: 9 минут
Наибольшая общая подпоследовательность: алгоритм и пример

Наибольшая общая подпоследовательность двух последовательностей - самая длинная цепочка элементов, которая встречается в каждой из них в том же порядке. Элементы разрешено пропускать: например, для слов «КОТ» и «КРОТ» ответом будет «КОТ», если во втором слове удалить «Р». Задача возникает при сравнении текстов, последовательностей событий и данных. В калькуляторе можно менять длины исходных слов и смотреть, как растёт таблица ответов для их начальных частей.

Подпоследовательность и подстрока

Подпоследовательность получают из исходной последовательности удалением любого числа элементов без перестановки оставшихся. У слова «КРОТ» есть подпоследовательности «КОТ», «КРТ» и «РОТ». Пустая последовательность тоже допустима: она получается удалением всех символов.

Подстрока устроена строже: её символы должны идти подряд. «КОТ» - подпоследовательность «КРОТ», но не его подстрока, поскольку между «К» и «О» стоит «Р». Эта разница меняет и ответ, и алгоритм. Для сравнения, алгоритм Кнута - Морриса - Пратта ищет вхождение образца как непрерывного фрагмента текста, а здесь пропуски разрешены в обеих последовательностях.

В аббревиатуре LCS английское longest common subsequence означает именно наибольшую общую подпоследовательность. «Общая» требует одного и того же порядка в обеих строках: буквы «АБ» не образуют общую подпоследовательность строк «АБ» и «БА». Зато каждая из букв по отдельности подходит; обе дают максимальную длину 1. Поэтому корректнее говорить об одной из наибольших общих подпоследовательностей: ответ может быть не единственным.

Идея таблицы: решения для префиксов

Пусть первая строка AA имеет длину mm, вторая BB - длину nn. Префикс длины ii состоит из первых ii символов строки. Обозначим через D[i,j]D[i,j] длину наибольшей общей подпоследовательности префиксов AA длины ii и BB длины jj. Полный ответ по длине находится в клетке D[m,n]D[m,n].

Если хотя бы один префикс пуст, общая подпоследовательность может быть только пустой: D[0,j]=D[i,0]=0D[0,j]=D[i,0]=0. Эти нули дают начальные значения. Каждая следующая клетка зависит от уже посчитанных соседей сверху, слева и по диагонали сверху слева. Поэтому таблицу удобно заполнять сверху вниз и слева направо.

Здесь проявляется приём динамического программирования: большая задача разбивается на повторяющиеся подзадачи, а их ответы сохраняются. Без запоминания наивная рекурсия многократно решает одни и те же задачи для одинаковых пар префиксов.

Золотая клетка проходит от полного ответа к пустым префиксам: диагональный шаг сохраняет совпадающую букву, а шаг в сторону пропускает лишний символ.

На обратном ходе видео шаги показаны в обратном порядке, чтобы цикл начинался и заканчивался в одной клетке. Рабочий алгоритм восстановления идёт от правого нижнего угла к левому верхнему.

Рекуррентная формула

Обозначим последние символы рассматриваемых префиксов через AiA_i и BjB_j, нумеруя символы с единицы. Тогда при i,j>0i,j>0:

D[i,j]={D[i−1,j−1]+1,Ai=Bj,max⁡(D[i−1,j],D[i,j−1]),Ai≠Bj.D[i,j]=\begin{cases} D[i-1,j-1]+1, & A_i=B_j,\\ \max(D[i-1,j],D[i,j-1]), & A_i\ne B_j. \end{cases}

Если последние символы равны, одну оптимальную подпоследовательность можно закончить этим общим символом. До него остаются два укороченных префикса, так что берём диагональную клетку и прибавляем единицу. Если символы различны, оба одновременно завершать общую подпоследовательность не могут. Достаточно сравнить два варианта: пропустить последний символ первой строки или последней второй. Большая из полученных длин и есть ответ.

Равенство соседних значений во втором случае не означает ошибку. Два направления могут вести к разным оптимальным ответам. Для вычисления длины достаточно выбрать любое из них; для перечисления всех ответов нужно изучать обе ветви и устранять повторы.

Пример: «КОТ» и «КРОТ»

Поместим «КОТ» по строкам, «КРОТ» по столбцам. Символ ∅\varnothing обозначает пустой префикс. Получается таблица:

Префикс A / префикс B∅ККРКРОКРОТ
∅00000
К01111
КО01122
КОТ01123
Таблица длин общих подпоследовательностей префиксов КОТ и КРОТ: итоговая клетка равна трём
Таблица длин общих подпоследовательностей префиксов КОТ и КРОТ: итоговая клетка равна трём

В клетке для «К» и «К» символы совпадают: диагональный ноль превращается в единицу. Для «КО» и «КР» последние символы различны, поэтому максимум верхней и левой клеток равен 1. Затем «О» совпадает с «О»: диагональная единица даёт 2. Наконец, совпадение «Т» с «Т» увеличивает диагональную двойку до 3.

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

Как восстановить сами символы

Число в последней клетке сообщает длину, но не выписывает последовательность. Начните с i=mi=m, j=nj=n и идите к границе таблицы. При равенстве символов запишите этот символ и перейдите по диагонали к D[i−1,j−1]D[i-1,j-1]. При несовпадении перейдите к большему из соседей сверху и слева; при равенстве выберите любой. Остановитесь, когда один индекс станет нулём, и переверните записанные символы: они собирались с конца.

Для нашего примера сначала совпадают последние «Т», затем «О». На паре префиксов «К» и «КР» символы различаются, и шаг влево пропускает «Р». После совпадения «К» получаем в обратном порядке «ТОК»; разворот даёт «КОТ». Позиции совпадений - 1, 2, 3 в первом слове и 1, 3, 4 во втором. Порядок строго возрастает в каждой строке.

В калькуляторе при равных соседях выбран переход вверх. Это правило делает результат воспроизводимым, но другой допустимый выбор тоже может дать оптимальную последовательность той же длины.

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

При повторяющихся символах одна и та же последовательность может получаться разными наборами позиций. Это ещё одно различие между подсчётом ответов и подсчётом способов их выбрать. Если задача просит все различные последовательности, повторяющиеся результаты из разных путей восстановления следует объединять.

Реализация и оценка сложности

Вот компактный вариант на Python. Он возвращает длину и один ответ; строки можно заменить списками сопоставимых элементов.

def lcs(a, b):
    m, n = len(a), len(b)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1] + 1
            else:
                d[i][j] = max(d[i - 1][j], d[i][j - 1])

    i, j, answer = m, n, []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            answer.append(a[i - 1])
            i -= 1
            j -= 1
        elif d[i - 1][j] >= d[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return d[m][n], answer[::-1]

В таблице (m+1)(n+1)(m+1)(n+1) клеток, а заполнение каждой внутренней клетки занимает постоянное время при постоянной стоимости сравнения элементов. Время - O(mn+m+n)O(mn+m+n), что для непустых входов записывают как O(mn)O(mn); память полной таблицы - O((m+1)(n+1))O((m+1)(n+1)). Обратный проход занимает не более m+nm+n шагов, а сам ответ хранит до min⁡(m,n)\min(m,n) элементов.

Если нужна только длина, достаточно хранить предыдущую и текущую строки таблицы. Разместив более короткую последовательность по столбцам, можно сократить рабочую память до O(min⁡(m,n)+1)O(\min(m,n)+1). Однако обычный обратный проход по полной таблице тогда недоступен: для восстановления придётся хранить дополнительную информацию или пересчитывать подзадачи. В лекции MIT о LCS та же идея изложена через подзадачи для суффиксов; выбор префиксов меняет направление обхода, но не суть.

Где применяется сравнение последовательностей

В сравнении версий текста общая подпоследовательность строк или символов помогает выделить сохранившиеся части. Если разрешены только вставки и удаления отдельных элементов, минимальное число таких операций для перехода от AA к BB равно m+n−2Lm+n-2L, где LL - длина НОП. Для «КОТ» и «КРОТ» это 3+4−2⋅3=13+4-2\cdot3=1: достаточно вставить «Р». При разрешённых заменах за одну операцию эта формула уже не описывает обычное расстояние редактирования.

В биоинформатике последовательности могут состоять из нуклеотидов или аминокислот; НОП служит одной из простых моделей сходства. Реальное выравнивание часто требует весов замен и штрафов за пропуски, которых в базовой постановке нет. Аналогично в задачах на палиндром строки важно сначала точно определить допустимые операции, а затем выбирать подходящий алгоритм.

Наконец, НОП отличается от поиска точного образца: алгоритм Рабина - Карпа сравнивает непрерывные фрагменты с помощью хеширования. Одинаковое слово «строка» в постановках не делает эти задачи взаимозаменяемыми.

Частые ошибки

  • Запрещать пропуски. Тогда решается задача об общей подстроке, а не подпоследовательности.
  • Переставлять символы. Общий набор букв ещё не гарантирует общего порядка.
  • Считать совпадения по диагонали независимо от таблицы. Нужно брать длину для соответствующих предыдущих префиксов и прибавлять единицу.
  • Ожидать единственного ответа. При равных вариантах могут существовать разные оптимальные цепочки.
  • Читать записанные при восстановлении буквы сразу. Обход с конца выдаёт их в обратном порядке.

FAQ

Что будет, если общих символов нет?

Все значения таблицы останутся нулями, длина ответа равна нулю, а сама общая подпоследовательность пуста.

Можно ли применять алгоритм к числам?

Да. Элементами могут быть числа, слова или другие объекты, если определено их сравнение на равенство. Порядок элементов по-прежнему нужно сохранять.

Сколько существует оптимальных ответов?

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

Коротко

НОП сохраняет порядок элементов и допускает пропуски. Таблица динамического программирования находит оптимальную длину по парам префиксов, а обратный проход восстанавливает один ответ. Для «КОТ» и «КРОТ» длина равна 3, а ответ - «КОТ».

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

8 ноября 20269 минут
Количество путей в ориентированном графе

Количество путей в ориентированном графе

Как найти количество путей в ориентированном графе: подсчёт в DAG, динамическое программирование, матрица смежности, заданная длина и влияние циклов на ответ.

8 ноября 20268 минут
Проверка палиндрома строки: два указателя и Python

Проверка палиндрома строки: два указателя и Python

Проверка палиндрома строки двумя указателями: пошаговый пример, код на Python, сложность, обработка пробелов и регистра, граничные случаи и особенности Unicode.

8 ноября 20268 минут
Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые без учёта порядка: примеры, отличие от упорядоченных сумм, рекуррентная формула и алгоритм динамического программирования.

8 ноября 20269 минут
Задача о рюкзаке: динамическое программирование

Задача о рюкзаке: динамическое программирование

Разбор задачи о рюкзаке (0/1 Knapsack) методом ДП: таблица dp[i][w], рекуррентный переход, traceback-восстановление набора. Пошаговые примеры и анализ сложности O(n*W).

17 июня 20267 минут
Алгоритм Рабина-Карпа: поиск подстроки за O(n+m)

Алгоритм Рабина-Карпа: поиск подстроки за O(n+m)

Разбираем алгоритм Рабина-Карпа: как полиномиальный хеш и скользящее окно ускоряют поиск подстроки до O(n+m) в среднем, почему бывают ложные совпадения и при чём тут плагиат.

31 мая 20269 минут