Najdłuższy wspólny podciąg¶
Podciąg to sekwencja znaków wybrana z tekstu bez zmiany ich kolejności, niekoniecznie znajdujących się obok siebie. Najdłuższy wspólny podciąg to problem znalezienia najdłuższego podciągu, który jest wspólny dla dwóch tekstów.
Specyfikacja¶
Dane¶
- \(a, b\) - dwa ciągi znaków
Wynik¶
- Najdłuższy wspólny podciąg ciągów \(a\) i \(b\)
Przykład¶
Dane¶
Wynik¶
"ittn"
Algorytm¶
Lista kroków¶
-
Utworzenie tabeli: stwórz tablicę o wymiarach
(m+1) x (n+1)
, gdziem
in
to długości dwóch porównywanych tekstów. Elementtab[i][j]
będzie przechowywał długość najdłuższego wspólnego podciągu dla kolejnych fragmentów zadanych tekstów: doi-tego
znaku pierwszego tekstu ij-tego
znaku drugiego tekstu. -
Inicjalizacja: ustaw wszystkie elementy pierwszej kolumny i pierwszego wiersza na 0.
-
Wypełnienie tabeli:
-
Dla każdego
i
od 1 dom
i każdegoj
od 1 don
:- Jeśli znaki na pozycji
i
pierwszego tekstu i pozycjij
drugiego tekstu są takie same, totab[i][j] = tab[i-1][j-1] + 1
. - W przeciwnym przypadku
tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
.
- Jeśli znaki na pozycji
-
Wyznaczenie wyniku:
- Odczytaj prawy dolny element tablicy - będzie to długość najdłuższego wspólnego podciągu.
- W oparciu o wartości w tablicy odtwórz najdłuższy wspólny podciąg.
Złożoność¶
Złożoność czasowa algorytmu to O(mn)
, gdzie m
i n
to długości analizowanych tekstów. Złożoność pamięciowa to również O(mn)
z uwagi na wymagania tablicy.