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.

Specification

Input

• \(a, b\) - dwa ciągi znaków

Output

• Najdłuższy wspólny podciąg ciągów \(a\) i \(b\)

Example

Input

a := "kitten"
b := "sitting"

Output

"ittn"

Algorytm

List of steps

1. Utworzenie tabeli: stwórz tablicę o wymiarach (m+1) x (n+1), gdzie m i n to długości dwóch porównywanych tekstów. Element tab[i][j] będzie przechowywał długość najdłuższego wspólnego podciągu dla kolejnych fragmentów zadanych tekstów: do i-tego znaku pierwszego tekstu i j-tego znaku drugiego tekstu.

2. Inicjalizacja: ustaw wszystkie elementy pierwszej kolumny i pierwszego wiersza na 0.

3. Wypełnienie tabeli:

4. Dla każdego i od 1 do m i każdego j od 1 do n:

   • Jeśli znaki na pozycji i pierwszego tekstu i pozycji j drugiego tekstu są takie same, to tab[i][j] = tab[i-1][j-1] + 1.
   • W przeciwnym przypadku tab[i][j] = max(tab[i - 1][j], tab[i][j - 1]).

5. Wyznaczenie wyniku:

6. Odczytaj prawy dolny element tablicy - będzie to długość najdłuższego wspólnego podciągu.
7. W oparciu o wartości w tablicy odtwórz najdłuższy wspólny podciąg.

Complexity

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.

Implementation

C++

Python