Наибольшая общая подпоследовательность
Определяйте рекуррентное соотношение LCS для двух строк, заполняйте двумерную таблицу и восстанавливайте саму подпоследовательность, двигаясь по таблице назад
«Наибольшая общая подпоследовательность» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Что такое подпоследовательность?
Подпоследовательность строки получается удалением некоторых (или всех) символов без изменения порядка оставшихся символов. Например, «ACE» является подпоследовательностью «ABCDE», а «AEC» — нет (порядок нарушен). Наибольшая общая подпоследовательность (LCS) двух строк — это самая длинная подпоследовательность, которая встречается в обеих строках. Строки «ABCBDAB» и «BDCABA» имеют LCS «BCBA» или «BDAB» длиной 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueВывод рекуррентной формулы LCS
Определим dp[i][j] как длину LCS для text1[:i] и text2[:j]. Если символы совпадают (text1[i-1] == text2[j-1]), увеличим длину LCS на 1: dp[i][j] = dp[i-1][j-1] + 1. Если они не совпадают, выберем лучший вариант: пропустить символ из одной из строк: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Базовый случай: dp[0][j] = dp[i][0] = 0 (LCS пустой строки имеет длину 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Трассировка таблицы LCS
Для text1='ABCD' и text2='ACBD' начните со строки и столбца нулей. Когда символы совпадают (A-A, C-C, B-B, если находятся в правильной позиции, D-D), dp[i][j] = dp[i-1][j-1] + 1. В противном случае берите максимум из левого и верхнего соседних значений. Просмотр заполненной таблицы показывает, как диагональные переходы соответствуют совпадающим символам. Итоговое значение dp[4][4] даёт длину LCS.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Восстановление самой LCS
Чтобы восстановить саму строку LCS, выполните обратный проход по таблице DP, начиная с dp[m][n]. Если text1[i-1] == text2[j-1], этот символ входит в LCS — запишите его и перейдите по диагонали к (i-1, j-1). Если dp[i-1][j] > dp[i][j-1], перейдите вверх; в противном случае — влево. В конце разверните собранные символы, поскольку проход выполнялся в обратном направлении. Это восстановление выполняется за O(m+n).
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABОптимизация памяти до O(n)
В таблице LCS нужны только текущая и предыдущая строки. Можно использовать одномерный массив размера n+1 и переменную diagonal, чтобы хранить значение dp[i-1][j-1] до его перезаписи. Обрабатывайте каждую строку слева направо. После обработки каждой ячейки обновлённое значение dp[j] соответствует текущей строке, а предыдущее значение нужно сохранить в diagonal перед перезаписью.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4Связь LCS и расстояния редактирования
LCS тесно связана с расстоянием редактирования (расстоянием Левенштейна). Если известна LCS, минимальное расстояние редактирования можно вычислить, используя только вставки и удаления: edit_dist = m + n - 2 * LCS(s1, s2). Для каждого символа из s1, не входящего в LCS, требуется удаление, а для каждого символа из s2, не входящего в LCS, — вставка. Замена здесь не учитывается, поскольку разрешены только вставка и удаление, но эта формула полезна для связанных задач.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Операция удаления для двух строк
Операция удаления для двух строк (LeetCode 583) требует найти минимальное число удалений, необходимых, чтобы сделать две строки одинаковыми. Сохраняемые символы должны образовывать общую подпоследовательность, поэтому нужно максимизировать LCS и удалить всё остальное. Ответ: m + n - 2 * LCS(s1, s2). Это эквивалентно описанному выше расстоянию редактирования со вставками и удалениями. Представление задач через LCS — мощный приём сведения.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Наибольшая общая подстрока
Не путайте LCS (подпоследовательность) с наибольшей общей подстрокой. Подстрока должна быть непрерывной, поэтому при несовпадении символов счётчик сбрасывается в 0, а не заменяется максимумом соседних значений. Рекуррентное соотношение меняется так: если символы совпадают, dp[i][j] = dp[i-1][j-1] + 1; иначе dp[i][j] = 0. Отслеживайте максимальное значение среди всех ячеек.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS для сравнения последовательностей
LCS широко используется в инструментах diff (например, в системе «Юникс» diff) для сравнения файлов. Сценарий изменений между двумя файлами строится на основе LCS: строки, входящие в LCS, не изменяются, дополнительные строки из первого файла удаляются, а дополнительные строки из второго файла вставляются. Понимание LCS помогает разобраться, как системы контроля версий отслеживают изменения и почему возникают конфликты при слиянии.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Кратчайшая общая надпоследовательность
Кратчайшая общая надпоследовательность (LeetCode 1092) — это самая короткая строка, содержащая и s1, и s2 в качестве подпоследовательностей. Каждый символ LCS появляется в надпоследовательности один раз; символы обеих строк, не входящие в LCS, необходимо добавить. Длина = m + n - LCS(s1, s2). Для восстановления используйте тот же обратный проход по LCS, но добавляйте символы обеих строк в позициях несовпадений.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5Сложность LCS и советы для собеседования
Классический алгоритм LCS выполняется за время O(m×n) и с использованием памяти O(m×n); приём со скользящим массивом позволяет уменьшить расход памяти до O(min(m,n)). Основные советы для собеседования: (1) Перед написанием кода чётко определите, что означает состояние DP. (2) Различайте случаи совпадения и отсутствия совпадения. (3) Если нужно восстановить последовательность, сначала опишите обратный проход, а затем запрограммируйте его. (4) Упомяните наибольшую возрастающую подпоследовательность (LIS) как связанную одномерную задачу, которую можно решить за O(n log n) с помощью сортировки терпеливого пасьянса.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Быстрая проверка
Проверьте, насколько хорошо Вы понимаете концепции курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали, что LCS использует dp[i][j] = dp[i-1][j-1]+1 при совпадении, а в противном случае — max(dp[i-1][j], dp[i][j-1]), сама последовательность восстанавливается обратным проходом по диагонали при совпадениях и в направлении большего соседнего значения при несовпадениях, а LCS лежит в основе расстояния редактирования, операций удаления, кратчайшей общей надпоследовательности и инструментов diff. Далее мы выведем рекуррентное соотношение для расстояния редактирования (Левенштейна), добавляющее операции замены в основу LCS.
Часто задаваемые вопросы
Урок «Наибольшая общая подпоследовательность» бесплатный?
Да — полный текст урока «Наибольшая общая подпоследовательность» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Наибольшая общая подпоследовательность»?
Определяйте рекуррентное соотношение LCS для двух строк, заполняйте двумерную таблицу и восстанавливайте саму подпоследовательность, двигаясь по таблице назад Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Наибольшая общая подпоследовательность»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Уникальные пути и минимальная сумма пути на сетках
- Наибольшая общая подпоследовательность
- Расстояние редактирования (Левенштейна)
- Оптимизация памяти для двумерного DP