Wolna encyklopedia

 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 wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

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ść.

Spis treści

Algorytm znajdujący tablicę długości NWP dwóch ciągów

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.

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

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]\}

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}

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. analogiczne rozumowanie można przeprowadzić dla C[0][j] (\forall_{j \in <0\cdots m>} C[0][j]\ =\ 0).

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

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.

Stub sekcji Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.
Źródło: „haslo,Najd%C5%82u%C5%BCszy_wsp%C3%B3lny_podci%C4%85g”