Longest Common Subsequence

Q: Какова временная сложность алгоритма поиска наибольшей общей подпоследовательности?

Табличное решение работает за время O(n × m) : по одной ячейке на каждую пару префиксов. Для полной таблицы требуется O(n × m) памяти, а при использовании двух строк — O(min(n, m)) . Обычная рекурсия без таблицы имеет экспоненциальную сложность.

СреднеДинамическое программирование

+10

Даны две строки, text1 и text2. Подпоследовательность строки сохраняет некоторые её буквы в исходном порядке, а остальные пропускает; сохранённые буквы не обязательно должны стоять рядом. Верните длину самой длинной строки, которая является подпоследовательностью обеих строк, или 0, если в этих двух строках нет общих букв.

Функция

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: первая строка
text2string: вторая строка
Возвращаетinteger: длина наибольшей общей подпоследовательности

Ограничения

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Обе строки содержат только строчные буквы английского алфавита.

Примеры

Ввод: text1 = "stone"text2 = "longest"
Вывод: 3
Пояснение: o, n, e появляются в этом порядке в обоих словах, поэтому one — общая последовательность длиной 3. Буквы s и t стоят в конце слова longest, но в начале слова stone, поэтому их использование даст не более st.

Ввод: text1 = "pear"text2 = "reap"
Вывод: 2
Пояснение: ea встречается в обоих словах. Буквы p и r стоят по разные стороны от ea в двух словах, поэтому ни одна из них не может присоединиться к нему, и ответ — 2.

Дополнительный вопрос

Можешь вернуть одну самую длинную общую подпоследовательность вместе с её длиной?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Жадное сопоставление не срабатывает: сопоставление c из cab с последней c из abc не оставляет ничего для a и b; если пропустить её, находится ab. Ответ для двух префиксов зависит от ответов для более коротких префиксов, поэтому таблица (n+1) × (m+1) позволяет решить каждую пару ровно один раз. Каждая строка использует только строку выше, поэтому достаточно двух строк.

Сравните первые буквы с помощью рекурсии

Верно, но не успевает на самых больших тестах

Идея

Пусть lcs(i, j) — ответ для суффиксов text1[i:] и text2[j:]. Если их первые буквы совпадают, объединим их в пару: у наибольшей общей подпоследовательности, пропускающей эту пару, можно заменить первую пару на эту, и её длина не уменьшится. Поэтому ответ равен 1 + lcs(i+1, j+1).

Если буквы различаются, их нельзя использовать обе, потому что соответствующие им буквы образовали бы пересекающиеся пары. Значит, одну из них можно пропустить: max(lcs(i+1, j), lcs(i, j+1)). Для пустого суффикса ответ равен 0.

При каждом несовпадении выполняются два вызова. Для двух строк длиной 20 букв без общих букв потребуется около 2.8 × 10^11 вызовов, хотя существует всего (n+1) × (m+1) различных пар (i, j), поэтому почти каждый вызов повторяет предыдущий.

Алгоритм

Запиши lcs(i, j) для суффиксов, начинающихся с i и j.
Если i или j выходит за конец своей строки, верни 0.
Если text1[i] == text2[j], верни 1 + lcs(i+1, j+1).
Иначе верни max(lcs(i+1, j), lcs(i, j+1)).
Ответ — lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Заполни таблицу префиксов

Идея

Пусть dp[i][j] — ответ для первых i букв text1 и первых j букв text2, поэтому индекс 0 означает пустой префикс, а строка 0 и столбец 0 равны 0. Сравним последние буквы двух префиксов — text1[i-1] и text2[j-1]: совпадающие буквы образуют пару, dp[i-1][j-1] + 1; если буквы разные, пропустим одну из них, max(dp[i-1][j], dp[i][j-1]). Это рекурсия, прочитанная с конца.

Каждая ячейка использует ячейки сверху, слева и по диагонали сверху слева, поэтому при заполнении по строкам, слева направо, они всегда уже вычислены. Для pear и reap строка для pea — [0, 0, 1, 2, 2]; её ячейка для rea равна 2, потому что a совпадает с a, и к ячейке для pe и re прибавляется единица.

Для двух строк длиной 1000 букв потребуется около 10^6 шагов с постоянным временем выполнения.

Алгоритм

Создай таблицу dp из (n+1) × (m+1) нулей.
Для i от 1 до n и j от 1 до m сравни text1[i-1] с text2[j-1].
При совпадении установи dp[i][j] = dp[i-1][j-1] + 1.
Иначе установи dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Верни dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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])
    return dp[n][m]

Оставь только две строки

Идея

После завершения строки строки выше неё больше никогда не читаются. Храни prev для завершённой строки, а cur — для заполняемой, и меняй их местами после каждой строки. Рекуррентное соотношение и порядок остаются прежними.

Ответ не зависит от того, какая строка идёт первой, поэтому пусть строки идут вдоль более короткой. Тогда в каждой строке будет min(n, m) + 1 чисел: 1001 вместо миллиона ячеек для самых больших входных данных, при тех же 10^6 шагах.

Алгоритм

Если text2 длиннее, чем text1, поменяй их местами.
Создай prev и cur, каждый из которых содержит m + 1 нулей, где m — длина более короткого текста.
Для каждой буквы в text1 заполни cur[1..m] по тому же правилу, что и в таблице, считывая значения из prev для строки выше.
Поменяй prev и cur местами.
Верни prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Ловушки и крайние случаи

Смешение индексов таблицы с индексами строк. Ячейка dp[i][j] сравнивает text1[i-1] с text2[j-1], поскольку строка 0 соответствует пустому префиксу.
При совпадении прибавление единицы к max(dp[i-1][j], dp[i][j-1]) вместо dp[i-1][j-1]. В таком случае одна буква может быть использована дважды: для aa и a будет возвращено 2 вместо 1.
Запись в строку, из которой вы ещё читаете. При использовании двух строк каждое значение из строки выше должно браться из prev, а cur[0] должно оставаться равным 0.
Мемоизация рекурсии в Python для строк длиной 1000 символов. Глубина вызовов достигает 2000, что превышает стандартный предел 1000.

Частые вопросы3

Какова временная сложность алгоритма поиска наибольшей общей подпоследовательности?

Табличное решение работает за время O(n × m): по одной ячейке на каждую пару префиксов. Для полной таблицы требуется O(n × m) памяти, а при использовании двух строк — O(min(n, m)). Обычная рекурсия без таблицы имеет экспоненциальную сложность.

В чём разница между наибольшей общей подпоследовательностью и наибольшей общей подстрокой?

Подпоследовательность может пропускать буквы, если их порядок сохраняется; подстрока — это блок соседних букв. Для stone и longest наибольшая общая подпоследовательность — one (3), а наибольшая общая подстрока — on (2). В таблице подстрок ячейка при несовпадении сбрасывается до 0, а не копирует значение соседней ячейки.

Как LCS связан с инструментами diff и расстоянием редактирования?

Различие между двумя версиями файла сохраняет их наибольшую общую подпоследовательность строк и показывает все остальные строки как добавленные или удалённые. Минимальное количество вставок и удалений, необходимое, чтобы преобразовать одну строку в другую, равно n + m - 2 × LCS. Расстояние редактирования также допускает замену буквы, поэтому для него нужна отдельная таблица.

def longestCommonSubsequence(text1, text2):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

text1 = "stone"
text2 = "longest"

Ожидаемый вывод

Longest Common Subsequence

Функция

Ограничения

Примеры

Подсказки

Решение

Сравните первые буквы с помощью рекурсии

Заполни таблицу префиксов

Оставь только две строки

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи