Najdłuższy wspólny podciąg
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: angielska wikipedia mówi: It should not be confused with the longest common substring problem (substrings are necessarily contiguous). Na wstępie jest jednak przykład substringowy.... Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Najdłuższy wspólny podciąg dla danych dwóch ciągów ich najdłuższym wspólnym podciągiem nazywamy ten z ich wspólnych podciągów, który ma największą długość.
- Dla ciągów abaabbaaa i babab ich NWP to baba.
- Dla ciągów POLITECHNIKA i TOALETA ich NWP to OLTA i OLEA.
- Dla ciągów 123 oraz 543 ich NWP to 3.
Spis treści |
[edytuj] Algorytm znajdujący tablicę długości NWP dwóch ciągów
[edytuj] Idea
Problem NWP dwóch ciągów A i B o długościach odpowiednio n i m może być rozwiązany za pomocą metody programowania dynamicznego.
Algorytm ten tworzy tablicę dwuwymiarową C[0..n][0..m]] taką, że wartość C[i][j] jest długością NWP podciągów A[1..i] i B[1..j]. A więc po zakończeniu wypełniania tablicy C komórka C[n][m] będzie zawierała wartość będąca długością NWP oryginalnych ciągów wejściowych A i B.
[edytuj] Optymalne rozwiązanie podproblemów
Załóżmy, że w danym kroku algorytmu chcemy obliczyć wartość komórki C[i][j], tj. długość NWP dla podciągów A[0..i] i B[0..j]. Jeżeli A i B są identyczne na pozycjach odpowiednio i i j (A[i]=B[j]) to należy włączyć ten wspólny znak do znalezionego wcześniej wspólnego wspólnego podciągu. Wtedy
![\! C[i][j]\ =\ C[i-1][j-1]\ +\ 1](../../../../math/a/e/e/aeeae04345dbddf4924954511a31ccb1.png)
ponieważ długością NWP ciągów A[1..i] i B[1..j] będzie długość NWP podciągów A[1..i-1] i B[1..j-1] plus jeden wspólny element z pozycji A[i] i B[j].
Jeżeli znaki A[i] i B[j] są różne, to obliczenie C[i][j] sprowadza się do sprawdzenia, który z wspólnych podciągów słów A[1..i-1] i B[1..j] oraz A[1..i] i B[1..j-1] jest dłuższy, i włączenie go do tablicy wynikowej.
![C[i][j]\ =\max\ \{C[i][j-1],\ C[i-1][j]\}](../../../../math/7/7/2/772687fe6cb74ebaeaec20745baa7954.png)
A więc algorytm wypełniania tablicy C można zapisać jako:
![C[i][j] =
\begin{cases}
\ C[i-1][j-1] + 1, & \ A[i]=B[j]\\
\max\ \{C[i-1][j],\ C[i][j-1]\}, & \ A[i]\neq B[j]\\
\end{cases}](../../../../math/8/2/7/8272fa54909db620284ac1f25037ed4b.png)
[edytuj] Stany początkowe
Do obliczenia tablicy C potrzeba jeszcze tylko tzw. stanów początkowych, tj. wartości początkowych rekurencjnych wzrów na C[i][j]. Z obserwacji, iż C[i][0] będzie zawsze równe 0 (ponieważ długość NWP ciągu i znaków i ciągu pustego jest zawsze równa zero, ponieważ NWP jest wtedy ciągiem pustym) wynika, że ![\forall_{i \in <0\cdots n>} C[i][0]\ =\ 0](../../../../math/a/9/1/a913297742f964659045f5d137fe4f6b.png)
. analogiczne rozumowanie można przeprowadzić dla C[0][j] (![\forall_{j \in <0\cdots m>} C[0][j]\ =\ 0](../../../../math/f/1/3/f13e219ddd73c1254106f7438b3db446.png)
).
[edytuj] Algorytm w pseudokodzie
for i from 0 to n do: //wypelnienie stanow poczatkowych
C[i][0] = 0
for j from 1 to m do:
C[0][j] = 0
for i from 1 to n do:
for j from 1 to m do:
if A[i]==B[j]:
C[i][j] = C[i-1][j-1] + 1 // znaleziono kolejny element NWP
else:
C[i][j] = max(C[i-1][j],C[i][j-1]);
Po zakończeniu działania powyższej procedury komórka C[n][m] będzie zawierać długość NWP ciągów A i B
[edytuj] Algorytm odtwarzający NWP
Mając gotową tablicę C długości wspólnych podciągów podciągów A i B można łatwo odtworzyć NWP.
Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.
