Тренажёр

Нашли ошибку?

Восстановить общую подпоследовательность

СложнаяНайти ошибку2 ошибкиГлава 9

РешеноНашли ошибку?

#динамическое программирование#общая подпоследовательность#восстановление ответаid: ga-lcs-restore

Функция lcs(a, b) возвращает саму самую длинную общую подпоследовательность, а не только её длину. Сначала она заполняет таблицу, как в главе, затем проходит по ней от правого нижнего угла и собирает символы. Таблица заполняется верно, но при восстановлении есть две ошибки. Найдите и исправьте их.

Примеры

lcs("рыбак", "бирка")   # "рк" — или другая общая подпоследовательность длины 2
lcs("abcbdab", "bdcaba")   # одна из подпоследовательностей длины 4, например "bcba"

Правила

Если вариантов несколько, годится любой. Тесты проверяют, что ответ — общая подпоследовательность максимальной длины.

Решение

def lcs(a: str, b: str) -> str:
    """Одна из самых длинных общих подпоследовательностей a и b."""
    n, m = len(a), len(b)
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[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 -= 1
            j -= 1
        elif table[i - 1][j] <= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(result)

Вывод

tests.py — только для чтения
def _is_subsequence(s, text):
    it = iter(text)
    return all(ch in it for ch in s)


def _check(a, b, best):
    """best — длина самой длинной общей подпоследовательности (заранее посчитана)."""
    got = lcs(a, b)
    assert isinstance(got, str), f"ожидалась строка, получено {got!r}"
    assert _is_subsequence(got, a), f"{got!r} — не подпоследовательность {a!r}"
    assert _is_subsequence(got, b), f"{got!r} — не подпоследовательность {b!r}"
    assert len(got) == best, f"{a!r}/{b!r}: длина {len(got)}, а можно {best}: {got!r}"


def test_identical():
    """Одинаковые строки → сама строка"""
    got = lcs("abc", "abc")
    assert got == "abc", f"ожидалось 'abc', получено {got!r}"


def test_example_russian():
    """рыбак и бирка"""
    _check("рыбак", "бирка", 2)


def test_classic():
    """abcbdab и bdcaba → длина 4"""
    _check("abcbdab", "bdcaba", 4)


def test_empty_and_disjoint():
    """Пустая строка и строки без общих символов → ''"""
    assert lcs("", "abc") == "", "с пустой строкой — ''"
    assert lcs("abc", "xyz") == "", "без общих символов — ''"


def test_one_inside_other():
    """Одна строка — подпоследовательность другой"""
    got = lcs("axbycz", "abc")
    assert got == "abc", f"ожидалось 'abc', получено {got!r}"


def test_many_pairs():
    """Разные пары строк"""
    pairs = [("programming", "gaming", 6), ("ACCGGTCGAG", "GTCGTTCGGA", 6), ("aaab", "abbb", 2), ("xyzxyz", "zyxzyx", 3)]
    for a, b, best in pairs:
        _check(a, b, best)

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 lcs_restore.py — тесты те же, результат покажет ✓ / ✗ и итог.

Подсказка 1
Таблица заполняется правильно, ошибки — в проходе назад. Проверьте на паре, где ответ однозначен: «abc» и «abc».
Подсказка 2
Проход идёт от конца строк к началу. В каком порядке оказываются собранные символы?
Подсказка 3
Если символы не совпали, нужно идти туда, где значение в таблице больше: иначе часть подпоследовательности теряется.

solution.py

def lcs(a: str, b: str) -> str:
    """Одна из самых длинных общих подпоследовательностей a и b."""
    n, m = len(a), len(b)
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[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 -= 1
            j -= 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))