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;