Longest Common Subsequence

Q: Jaka jest złożoność czasowa problemu najdłuższego wspólnego podciągu?

Rozwiązanie z użyciem tabeli działa w czasie O(n × m) , po jednej komórce na każdą parę prefiksów. Pełna tabela wymaga O(n × m) pamięci, a dwa wiersze — O(min(n, m)) . Zwykła rekurencja bez tabeli ma złożoność wykładniczą.

ŚrednieProgramowanie dynamiczne

+10

Otrzymujesz dwa ciągi znaków: text1 i text2. Podciąg ciągu znaków zachowuje niektóre jego litery w ich pierwotnej kolejności i pomija pozostałe; zachowane litery nie muszą sąsiadować ze sobą. Zwróć długość najdłuższego ciągu znaków, który jest podciągiem obu ciągów, lub 0, jeśli oba ciągi nie mają żadnej wspólnej litery.

Funkcja

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

text1string: pierwszy ciąg znaków
text2string: drugi ciąg znaków
Zwracainteger: długość najdłuższego wspólnego podciągu

Ograniczenia

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Oba ciągi zawierają wyłącznie małe litery alfabetu angielskiego.

Przykłady

Wejście: text1 = "stone"text2 = "longest"
Wyjście: 3
Wyjaśnienie: o, n, e występują w tej kolejności w obu słowach, więc one jest wspólne, długość wynosi 3. Litery s i t występują na końcu longest, ale na początku stone, więc ich użycie daje co najwyżej st.

Wejście: text1 = "pear"text2 = "reap"
Wyjście: 2
Wyjaśnienie: ea występuje w obu słowach. Litery p i r znajdują się po przeciwnych stronach ea w obu słowach, więc żadna z nich nie może do niego dołączyć, a odpowiedź to 2.

Pytanie dodatkowe

Czy możesz zwrócić jedną najdłuższą wspólną podsekwencję wraz z jej długością?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Chciwe dopasowywanie zawodzi: dopasowanie c z cab do ostatniego c w abc nie pozostawia nic dla a i b; pominięcie go pozwala znaleźć ab. Odpowiedź dla dwóch prefiksów zależy od odpowiedzi dla krótszych prefiksów, więc tabela (n+1) × (m+1) rozwiązuje każdą parę dokładnie raz. Każdy wiersz odczytuje tylko wiersz powyżej, więc wystarczą dwa wiersze.

Porównuj pierwsze litery za pomocą rekurencji

Poprawne, ale nie kończy się na największych testach

Intuicja

Niech lcs(i, j) oznacza wynik dla sufiksów text1[i:] i text2[j:]. Jeśli ich pierwsze litery są takie same, połącz je w parę: najdłuższy wspólny podciąg pomijający tę parę może zamienić swoją pierwszą parę na tę, nie stając się krótszy. Zatem wynik to 1 + lcs(i+1, j+1).

Jeśli litery się różnią, nie można użyć obu, ponieważ ich odpowiedniki sprawiłyby, że pary by się krzyżowały. Można więc pominąć jedną z nich: max(lcs(i+1, j), lcs(i, j+1)). Pusty sufiks daje wynik 0.

Każda niezgodność rozpoczyna dwa wywołania. Dwa 20-literowe ciągi bez wspólnych liter wymagają już około 2.8 × 10^11 wywołań, a istnieje tylko (n+1) × (m+1) różnych par (i, j), więc niemal każde wywołanie powtarza wcześniejsze.

Algorytm

Napisz lcs(i, j) dla sufiksów zaczynających się na pozycjach i i j.
Jeśli i lub j wykracza poza koniec swojego ciągu znaków, zwróć 0.
Jeśli text1[i] == text2[j], zwróć 1 + lcs(i+1, j+1).
W przeciwnym razie zwróć max(lcs(i+1, j), lcs(i, j+1)).
Odpowiedzią jest 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)

Uzupełnij tabelę prefiksów

Intuicja

Niech dp[i][j] będzie wynikiem dla pierwszych i liter ciągu text1 i pierwszych j liter ciągu text2, gdzie indeks 0 oznacza pusty prefiks, a wiersz 0 i kolumna 0 zawierają same zera. Porównaj ostatnie litery obu prefiksów: text1[i-1] i text2[j-1]: równe litery tworzą parę, dp[i-1][j-1] + 1; różne litery — pomijamy jedną z nich, max(dp[i-1][j], dp[i][j-1]). To rekurencja odczytywana od końca.

Każda komórka odczytuje komórki powyżej, po lewej oraz po przekątnej w górę i w lewo, więc wypełnianie wiersz po wierszu, od lewej do prawej, zawsze zapewnia, że są już gotowe. Dla ciągów pear i reap wiersz dla pea to [0, 0, 1, 2, 2]; jego komórka dla rea ma wartość 2, ponieważ a pasuje do a, co dodaje jeden do komórki dla pe i re.

Dwa ciągi po 1000 liter wymagają około 10^6 kroków o stałym czasie.

Algorytm

Utwórz tablicę dp złożoną z (n+1) × (m+1) zer.
Dla i od 1 do n i j od 1 do m porównaj text1[i-1] z text2[j-1].
Jeśli są zgodne, ustaw dp[i][j] = dp[i-1][j-1] + 1.
W przeciwnym razie ustaw dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Zwróć 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]

Zachowaj tylko dwa wiersze

Intuicja

Gdy wiersz jest gotowy, wiersze nad nim nie są już nigdy odczytywane. Zachowaj prev dla ukończonego wiersza i cur dla wypełnianego wiersza, a po każdym wierszu zamień je miejscami. Zależność rekurencyjna i kolejność pozostają takie same.

Wynik nie zależy od tego, który ciąg jest pierwszy, więc pozwól, by wiersze przebiegały wzdłuż krótszego ciągu. Każdy wiersz zawiera wtedy min(n, m) + 1 liczb: 1001 zamiast miliona komórek dla największych danych wejściowych, przy tej samej liczbie 10^6 kroków.

Algorytm

Jeśli text2 jest dłuższy niż text1, zamień je miejscami.
Utwórz prev i cur, każdy z m + 1 zerami, gdzie m to krótsza długość.
Dla każdej litery text1 wypełnij cur[1..m] według tej samej zasady co w tabeli, odczytując prev z poprzedniego wiersza.
Zamień miejscami prev i cur.
Zwróć 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]

Pułapki i przypadki brzegowe

Mieszanie indeksów tablicy z indeksami ciągu znaków. Komórka dp[i][j] porównuje text1[i-1] z text2[j-1], ponieważ wiersz 0 odpowiada pustemu prefiksowi.
Przy zgodności dodawanie jedynki do max(dp[i-1][j], dp[i][j-1]) zamiast do dp[i-1][j-1]. Może to spowodować dwukrotne użycie tej samej litery: dla aa i a wynikiem byłoby 2 zamiast 1.
Zapisywanie wartości w wierszu, z którego nadal odczytujesz. Przy dwóch wierszach każda wartość z wiersza powyżej musi pochodzić z prev, a cur[0] musi pozostać równe 0.
Zapamiętywanie wyników rekurencji w Pythonie dla ciągów o długości 1000 znaków. Głębokość wywołań osiąga 2000, przekraczając domyślny limit 1000.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu najdłuższego wspólnego podciągu?

Rozwiązanie z użyciem tabeli działa w czasie O(n × m), po jednej komórce na każdą parę prefiksów. Pełna tabela wymaga O(n × m) pamięci, a dwa wiersze — O(min(n, m)). Zwykła rekurencja bez tabeli ma złożoność wykładniczą.

Czym różni się najdłuższy wspólny podciąg od najdłuższego wspólnego podciągu ciągłego?

Podciąg może pomijać litery, o ile zachowana jest ich kolejność; podciąg spójny to blok sąsiadujących liter. Dla stone i longest najdłuższy wspólny podciąg to one (3), ale najdłuższy wspólny podciąg spójny to on (2). W przypadku niezgodności tabela podciągów spójnych ustawia komórkę na 0 zamiast kopiować wartość z sąsiedniej komórki.

Jaki związek ma LCS z narzędziami diff i odległością edycyjną?

Różnica między dwiema wersjami pliku zachowuje najdłuższy wspólny podciąg ich wierszy i pokazuje każdy pozostały wiersz jako dodany lub usunięty. Najmniejsza liczba wstawień i usunięć potrzebnych do przekształcenia jednego ciągu w drugi wynosi n + m - 2 × LCS. Odległość edycyjna pozwala również na zastąpienie litery, dlatego wymaga własnej tabeli.

def longestCommonSubsequence(text1, text2):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

text1 = "stone"
text2 = "longest"

Oczekiwany wynik

Longest Common Subsequence

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Porównuj pierwsze litery za pomocą rekurencji

Uzupełnij tabelę prefiksów

Zachowaj tylko dwa wiersze

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania