Наибольшая общая подпоследовательность (LCS): разбор и код

Коротко

Задача

Даны две последовательности. Найти самую длинную последовательность, которая является подпоследовательностью обеих.

A = "ABCBDAB"
B = "BDCABA"

LCS = "BCBA"  (длина 4)

Ключевое слово — подпоследовательность: элементы не обязаны идти подряд, но порядок сохраняется.

подпоследовательность "ACE" в "ABCDE"  ✓  (пропускаем B и D)
подстрока           "ACE" в "ABCDE"    ✗  (не идут подряд)

Путаница между этими понятиями — источник большинства ошибок в задачах на строки.

Идея решения

Классическая двумерная динамика.

dp[i][j] — длина LCS первых i символов строки A и первых j символов строки B.

Переход рассуждается так. Смотрим на последние символы a[i-1] и b[j-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.

Реализация

def lcs_length(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[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[n][m]


print(lcs_length('ABCBDAB', 'BDCABA'))   # 4
print(lcs_length('AGGTAB', 'GXTXAYB'))   # 4  → GTAB

Таблица в действии

Для ABCBDAB и BDCABA:

      ''  B  D  C  A  B  A
  ''   0  0  0  0  0  0  0
  A    0  0  0  0  1  1  1
  B    0  1  1  1  1  2  2
  C    0  1  1  2  2  2  2
  B    0  1  1  2  2  3  3
  D    0  1  2  2  2  3  3
  A    0  1  2  2  3  3  4
  B    0  1  2  2  3  4  4

Ответ в правом нижнем углу — 4.

Восстановление подпоследовательности

Чаще нужна не длина, а сама последовательность. Идём по таблице от правого нижнего угла назад.

def lcs_string(a: str, b: str) -> str:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # разматываем назад
    result = []
    i, j = n, m

    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])       # символ вошёл в ответ
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1                        # пришли сверху
        else:
            j -= 1                        # пришли слева

    return ''.join(reversed(result))


print(lcs_string('ABCBDAB', 'BDCABA'))   # 'BCBA'
print(lcs_string('AGGTAB', 'GXTXAYB'))   # 'GTAB'

Ответ не единственный: у строк выше есть и другая общая подпоследовательность длины 4 — BDAB. Какую вернёт код, зависит от того, какое направление предпочитается при равенстве.

Экономия памяти

Если нужна только длина, полная таблица не требуется — достаточно двух строк.

def lcs_length_optimized(a: str, b: str) -> int:
    if len(a) < len(b):
        a, b = b, a          # меньшая строка задаёт ширину

    previous = [0] * (len(b) + 1)

    for ca in a:
        current = [0] * (len(b) + 1)
        for j, cb in enumerate(b, start=1):
            if ca == cb:
                current[j] = previous[j - 1] + 1
            else:
                current[j] = max(previous[j], current[j - 1])
        previous = current

    return previous[-1]

Память стала O(min(n, m)). Но восстановить сам ответ так уже не получится — для этого существует алгоритм Хиршберга, который использует принцип «разделяй и властвуй» и даёт восстановление при линейной памяти за то же O(n·m) времени.

Связь с diff

LCS — математическая основа утилиты diff и всех систем контроля версий.

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

def simple_diff(old: list[str], new: list[str]) -> list[str]:
    n, m = len(old), len(new)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if old[i - 1] == new[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    result = []
    i, j = n, m

    while i > 0 or j > 0:
        if i > 0 and j > 0 and old[i - 1] == new[j - 1]:
            result.append(f'  {old[i - 1]}')
            i, j = i - 1, j - 1
        elif j > 0 and (i == 0 or dp[i][j - 1] >= dp[i - 1][j]):
            result.append(f'+ {new[j - 1]}')
            j -= 1
        else:
            result.append(f'- {old[i - 1]}')
            i -= 1

    return result[::-1]


for line in simple_diff(['a', 'b', 'c'], ['a', 'x', 'c']):
    print(line)
#   a
# - b
# + x
#   c

Реальный diff использует более хитрый алгоритм Майерса, но принцип тот же.

LCS и расстояние Левенштейна

Задачи родственные, но не тождественные.

Если замены запрещены, между ними есть связь:

расстояние = n + m − 2 · LCS(a, b)

Мы удаляем всё лишнее из первой строки и вставляем недостающее во вторую.

Другие применения

Биоинформатика — сравнение последовательностей ДНК и белков. Алгоритм Нидлмана-Вунша это, по сути, LCS с весами.

Обнаружение плагиата — доля общей подпоследовательности как мера схожести текстов.

Слияние версий в системах контроля версий (трёхстороннее слияние).

Наибольшая возрастающая подпоследовательность сводится к LCS: достаточно взять исходный массив и его отсортированную копию. Правда, решать так неэффективно — O(n²) вместо O(n log n).

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

Путаница с подстрокой. Задача о наибольшей общей подстроке решается другой динамикой: там при несовпадении dp[i][j] = 0, а ответ — максимум по всей таблице, а не угол.

# наибольшая общая ПОДСТРОКА — другая задача
if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
    best = max(best, dp[i][j])
else:
    dp[i][j] = 0          # разрыв обнуляет

Возврат max(dp) вместо dp[n][m]. Для LCS ответ строго в правом нижнем углу — таблица монотонно неубывает.

Забытый разворот при восстановлении. Символы собираются с конца.

Смещение индексов. dp[i][j] соответствует символам a[i-1] и b[j-1].

Что запомнить

• LCS ищет общую подпоследовательность — элементы не обязаны идти подряд.
• Совпали символы — плюс один к диагонали; не совпали — максимум из верхнего и левого.
• Ответ находится в правом нижнем углу таблицы.
• Восстановление требует полной таблицы; для только длины хватит двух строк.
• LCS — основа diff и систем контроля версий.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→