LCS - najdłuższy wspólny podciąg

Romualda Laskowska

Niech W1 i W2 będą dwoma wyrazami (czyli ciągami liter). Mówimy, że W1 jest podciągiem W2 wtedy i tylko wtedy, gdy istnieje taki rosnący ciąg liczb naturalnych xi, że zachodzi:

W1[i] = W2[xi] dla wszystkich i=1…n, gdzie n to długość wyrazu W1, a W1[i] oznacza i-tą literkę z W1.

Czyli, w prostszych słowach, W1 jest podciągiem W2, jeśli potrafimy tak wybierać z W2 kolejne literki, aby utworzyć wyraz W1.

W2 = PRZEZIMOWAĆ

W1 = ZIMA

Zadanie:

Dla danych dwóch wyrazów A i B należy znaleźć najdłuższy taki wyraz P, aby P był podciągiem A i podciągiem B.

Załóżmy, że znamy długość najdłuższego wspólnego podciągu dla par prefiksów:
• Ai i Bj,
• Ai+1 i Bj,
• Ai i Bj+1.

a) Jeżeli A[i+1] = x i B[j+1] = x to LCS dla tych dwóch wyrazów może zostać utworzony poprzez dodanie literki x na koniec LCS dla wyrazów Ai i Bj. Dlaczego? Gdyby w najdłuższym wspólnym podciągu Ai+1 i Bj+1 nie było literki x na końcu, moglibyśmy go przedłużyć, dokładając doń ostatnią literkę Ai+1 i Bj+1,.Ale wtedy powstałby podciąg dłuższy od najdłuższego! Literka x musi być więc ostatnią literką każdego poprawnie wyliczonego LCS. Najmniej "utracimy" zatem jeśli źródłem literki X będą końce Ai+1 i Bj+1 - pozostanie wtenczas jeszcze i-literek prefiksu A i j-literek prefiksu B i z nich tworzyć będziemy resztę najdłuższego wspólnego podciągu.

RABARBA R
LABRADO R

Znaleziony LCS (tekst pogrubiony) można przedłużyć o wspólną literkę 'R'

b) Jeżeli A[i+1] = x a B[j+1] = y i x!=y to LCS dla Ai+1 i Bj+1 jest też LCS dla co najmniej jednej z dwóch par: Ai i Bj+1 lub Ai+1 i Bj. Skąd taki wniosek? Ostatnią literką najdłuższego wspólnego podciągu dla Ai+1 i Bj+1 nie mogą być jednocześnie x i y (bo to dwie różne literki). Zatem jeden z wyrazów Ai+1 i Bj+1 możemy bez żadnej straty pozbawić jego ostatniej literki. Nie wiemy jednak który z nich, zatem zwyczajnie sprawdzimy obie możliwości i wybierzemy tę, która daje lepszy wynik.

BATONI K
ANTONI

Najdłuższy wspólny podciąg dla "BATONIK" i "ATONI" jest jednocześnie najdłuższym wspólnym podciągiem "ANTONI" oraz "ATONI"

Czyli możemy z pewnością stwierdzić, że LCS (i+1, j+1) (tak będziemy od teraz oznaczać długość LCS dla pary Ai+1, Bj+1) to:

  • 1+LCS(i,j), jeśli A[i+1]=B[j+1] (przypadek a),
  • Max(LCS(i+1, j), LCS(i,j+1)), jeśli A[i+1]!=B[j+1](przypadek b).
  • LCS dla A0 i Bj zawsze składa się z zera literek. Jest to dość oczywiste - w A0 nie ma żadnej literki, więc nic dłuższego niż słowo puste nie może być podciągiem A0. Analogicznie: LCS dla Ai i B0 też ma zawsze zero literek. Prawdziwe są zatem następujące równości:
  • LCS (i,0) = 0 dla każdego naturalnego i
  • LCS (0,j) = 0 dla każdego naturalnego j

Aby wyliczyć wartość LSC, utworzymy tablicę o wymiarach n+1 na m+1 komórek, bowiem w komórce (i, j) chcemy przechowywać liczbę LCS (i, j) (dla i ε {0, 1, …, n} oraz j ε {0, 1, …, n}).

0 1 2 3 4 5 6 7 8
0
1
2
3
4
5
6
7
8

Skoro prawdą jest, że LCS (i,0) = 0 i LCS (0,j) = 0, to zerowy wiersz i zerową kolumnę tabeli wypełnić należy zerami.

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0

Wpisujemy zera.

Rozważam kolejno i-ty znak łańcucha A, porównuję z j-tym znakiem łańcucha B. Zauważ że:

  • Jeśli znaki są równe: A[i] = B[j], to max. długość wspólnego podciągu wzrasta o 1 w porównaniu z wynikiem dla stanu, gdy porównywaliśmy znaki A[i-1] i B[j-1], ostatnie ze znaków w obu łańcuchach krótszych o 1 znak.
  • Jeśli znaki są różne: A[i] != B[j], to max. długość wspólnego podciągu pozostaje na dotychczasowej wartości. Będzie to większa z wartości znajdujących się w sąsiednich polach tablicy W: w poprzednim wierszu lub w poprzedniej kolumnie.
for (int i=1; i<=na; i++) {
       char a = A[i-1];
       for (int j=1; j<=nb; j++) {
          char b = B[j-1];
          if (a==b) W[i][j] = W[i-1][j-1]+1;
            else 
            W[i][j] = max( W[i-1][j], W[i][j-1] );
       }
    }

Które znaki utworzyły najdłuższy wspólny podciąg?
Rozpoczynamy od porównania ostatnich znaków w obu łańcuchach: i=na; j=nb;

  • jeżeli znak Ai i Bj jest taki sam, to ten znak wchodzi do rozwiązania,
  • jeśli znaki są różne, to patrzymy z której strony przyszliśmy do pola Wi,j: z lewej kolumny czy z górnego wiersza:
  • jeśli Wi,j-1>Wi-1,j to znaczy że z lewej kolumny, więc bierzemy j=j-1
  • w przeciwnym razie idziemy do poprzedniego wiersza, tzn. bierzemy i=i-1
  • kontynuujemy dopóki i>0 oraz j>0
string s = "";
    int i = na;
    int j = nb;
    while (i>0 && j>0) {
       char a = A[i-1];
       char b = B[j-1];
       if (a==b) {s = a+s; // dodaj znak do wyniku
                 i--; j--;   // przejdź do poprzednich znaków w obu słowach A i B
                 }
          else
            if (W[i-1][j]>W[i][j-1]) // jeśli W z poprz.wiersz> W z poprz.kolumna
                i--;                 // przejdź do poprzedniego znaku w słowie A, 
            else j--;                // przejdź do poprzedniej znaku w słowie B
    }
    cout<<"Najdluzszy wspolny podciag = "<<s<<endl;
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License