Longest Common Substring

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

Rozwiązanie z użyciem programowania dynamicznego zajmuje O(n × m) czasu i O(m) pamięci przy użyciu jednego wiersza. Rozszerzanie od każdej pary początków zajmuje w najgorszym przypadku O(n × m × min(n, m)) . Automat sufiksowy osiąga złożoność około O(n + m) , kosztem znacznie dłuższego programu.

Q: Jak zwrócić najdłuższy wspólny podciąg?

Za każdym razem, gdy komórka ma wartość większą niż best , zapisz również pozycję i w s1 , w której kończy się ten blok. Na końcu podciąg to best liter z s1 , które się tam kończą. Ścisłe porównanie „większe niż” sprawia, że wybierany jest pierwszy znaleziony najdłuższy blok w s1 .

ŚrednieProgramowanie dynamiczne

+10

Otrzymujesz dwa ciągi znaków: s1 i s2. Podciąg to nieprzerwany ciąg liter pobrany z ciągu znaków, na przykład ork z clockwork. Znajdź najdłuższy podciąg wspólny dla s1 i s2 i zwróć jego długość. Jeśli żadna litera nie występuje w obu ciągach, odpowiedzią jest 0.

Funkcja

longestCommonSubstring(s1: string, s2: string) → integer

s1string: pierwszy ciąg znaków
s2string: drugi ciąg znaków
Zwracainteger: długość najdłuższego bloku liter występującego w obu ciągach

Ograniczenia

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 i s2 składają się z małych liter alfabetu angielskiego.

Przykłady

Wejście: s1 = "clockwork"s2 = "workshop"
Wyjście: 4
Wyjaśnienie: work zamyka clockwork i otwiera workshop, więc jest wspólnym podciągiem o długości 4 i żaden dłuższy fragment nie występuje w obu.

Wejście: s1 = "hammer"s2 = "harmed"
Wyjście: 2
Wyjaśnienie: ha i me występują w obu słowach, ale nie ma w nich żadnego ciągu trzech liter. Oba słowa zawierają litery h, a, m, e w tej kolejności, ale w słowie harmed między a i m znajduje się r.

Pytanie dodatkowe

Czy możesz przetestować, czy istnieje wspólny podciąg o danej długości L w czasie około O(n + m), używając haszowania kroczącego, a następnie przeprowadzić wyszukiwanie binarne po L?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Rozszerzanie dopasowania od każdej pary początków powoduje ponowne odczytywanie tych samych liter. Zamiast tego sprawdź, gdzie blok się kończy: wspólny blok kończący się na s1[i] i s2[j] jest o jedną literę dłuższy niż blok kończący się na dwóch poprzedzających je literach albo jest pusty, jeśli litery się różnią. Tablica tych długości pozwala uzyskać odpowiedź w czasie O(n × m).

Rozszerzaj z każdej pary pozycji początkowych

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

Intuicja

Każdy wspólny podciąg zaczyna się na jakiejś pozycji i w s1 i na jakiejś pozycji j w s2. Dla każdej pary przesuwaj się do przodu, dopóki litery są zgodne, i licz kroki; największa liczba kroków jest odpowiedzią.

Powtarzający się tekst wydłuża te przejścia. Gdy oba ciągi składają się z 1000 kopii a, każde przejście dla pary trwa aż do końca krótszego sufiksu: około 3.3 × 10^8 porównań liter. Przejście od (i, j) powtarza całe przejście od (i+1, j+1), o jedną literę później.

Algorytm

Ustaw best = 0.
Dla każdego i w s1 i każdego j w s2 ustaw k = 0.
Dopóki zarówno i+k, jak i j+k znajdują się w swoich ciągach znaków oraz s1[i+k] == s2[j+k], zwiększaj k o 1.
Zachowaj największą wartość k w best i ją zwróć.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabela długości bloków kończących się na każdej parze

Intuicja

Niech run[i][j] oznacza długość najdłuższego wspólnego fragmentu kończącego się dokładnie na s1[i-1] i s2[j-1]; wiersz 0 i kolumna 0 zawierają 0. Taki fragment musi zawierać obie litery. Jeśli się różnią, fragment nie istnieje i komórka ma wartość 0. Jeśli są takie same, fragment składa się z tej pary oraz fragmentu kończącego się o jedną literę wcześniej w obu ciągach: run[i-1][j-1] + 1. Każdy wspólny podciąg kończy się w jakimś miejscu, więc odpowiedzią jest największa komórka, niezależnie od jej położenia.

W przypadku hammer i harmed litery h dają 1, a litery a wydłużają fragment do 2, po czym r przerywa fragment. Drugie m w hammer napotyka m w harmed po niezgodności m i r, więc zaczyna od 1, a litery e zwiększają wartość do 2. Żadna komórka nie osiąga wartości 3.

Jedno porównanie na komórkę: około miliona dla dwóch ciągów o długości 1000 liter, niezależnie od tekstu.

Algorytm

Utwórz tablicę run z n+1 wierszami i m+1 kolumnami, wypełnioną zerami, i ustaw best = 0.
Przejdź pętlą przez i od 1 do n, a wewnątrz niej przez j od 1 do m, porównując s1[i-1] z s2[j-1].
Jeśli wartości są zgodne, ustaw run[i][j] = run[i-1][j-1] + 1 i zaktualizuj best.
Jeśli wartości się nie zgadzają, pozostaw komórkę równą 0.
Zwróć best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Jeden wiersz, aktualizowany od prawej do lewej

Intuicja

Każda komórka odczytuje tylko komórkę po przekątnej w górę i w lewo. Dlatego jedna tablica run z m+1 liczbami może przechowywać tabelę, jeśli odwiedzasz j od prawej do lewej: gdy zapisujesz run[j], komórka run[j-1] nadal zawiera wartość dla poprzedniej litery s1, czyli komórkę po przekątnej.

Niezgodność musi teraz jawnie zapisywać 0, ponieważ komórka nadal zawiera liczbę z poprzedniego wiersza. Czas działania pozostaje równy O(n × m), a pamięć spada z około 10^6 liczb do 1001.

Algorytm

Utwórz tablicę run złożoną z m+1 zer i ustaw best = 0.
Dla każdej litery ch z s1 odwiedzaj j od m w dół do 1.
Jeśli ch == s2[j-1], ustaw run[j] = run[j-1] + 1 i zaktualizuj best.
W przeciwnym razie ustaw run[j] = 0.
Zwróć best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Pułapki i przypadki brzegowe

Zwracanie ostatniej komórki. run[n][m] uwzględnia tylko bloki, które kończą się na obu ostatnich literach. Dla abc i abd wynosi 0, a dla ab wynosi 2.
Kopiowanie większego sąsiada w przypadku niezgodności. To reguła podciągu, która pozwala blokowi pomijać litery: dla hammer i harmed zwraca 4 zamiast 2.
Przechodzenie przez pojedynczy wiersz od lewej do prawej. Wartość na przekątnej zostaje nadpisana, zanim ją odczytasz, więc a w porównaniu z aa daje 2.
Pominięcie resetowania w pojedynczym wierszu. Długość z poprzedniej litery s1 zostaje zachowana i później przedłuża blok, którego tam nie ma.
Przechodzenie przez algorytm brute force bez sprawdzania granic. Dla zzzz w porównaniu z zz odczytuje dane poza końcem krótszego ciągu.

Najczęstsze pytania3

Jaka jest różnica między najdłuższym wspólnym podciągiem spójnym a najdłuższym wspólnym podciągiem?

Podciąg znaków to nieprzerwany ciąg liter; podciąg zachowuje kolejność, ale może zawierać przerwy. Dla hammer i harmed najdłuższy wspólny podciąg znaków ma długość 2, a najdłuższy wspólny podciąg ma długość 4 (hame). W tabelach niezgodność resetuje komórkę podciągu znaków do 0, ale sprawia, że komórka podciągu kopiuje większego sąsiada.

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

Rozwiązanie z użyciem programowania dynamicznego zajmuje O(n × m) czasu i O(m) pamięci przy użyciu jednego wiersza. Rozszerzanie od każdej pary początków zajmuje w najgorszym przypadku O(n × m × min(n, m)). Automat sufiksowy osiąga złożoność około O(n + m), kosztem znacznie dłuższego programu.

Jak zwrócić najdłuższy wspólny podciąg?

Za każdym razem, gdy komórka ma wartość większą niż best, zapisz również pozycję i w s1, w której kończy się ten blok. Na końcu podciąg to best liter z s1, które się tam kończą. Ścisłe porównanie „większe niż” sprawia, że wybierany jest pierwszy znaleziony najdłuższy blok w s1.

def longestCommonSubstring(s1, s2):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

s1 = "clockwork"
s2 = "workshop"

Oczekiwany wynik

Longest Common Substring

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rozszerzaj z każdej pary pozycji początkowych

Tabela długości bloków kończących się na każdej parze

Jeden wiersz, aktualizowany od prawej do lewej

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania