Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Rozwiązanie

    Zdefiniujmy najpierw jeszcze jedno pomocnicze pojęcie:

   Niech $ A_i $ będzie wyrazem złożonym z pierwszych $ i $ liter $ A $. $ A_i $ nazywamy prefiksem słowa $ A $. $ A_0 $ uznawać będziemy za wyraz złożony z zera liter (czyli słowo puste).


Przykładowe prefiksy wyrazu "makarony".

    Optymalny algorytm będzie wprost wynikał z dwóch prostych obserwacji.

Obserwacja pierwsza

    Załóżmy, że znamy długość najdłuższego wspólnego podciągu dla par prefiksów:

  • $ A_i $ i $ B_j $,
  • $ A_{i+1} $ i $ B_j $,
  • $ A_i $ i $ B_{j+1} $.

 

    Na podstawie powyższych informacji spróbujemy teraz wyliczyć długość LCS dla $ A_{i+1} $ i $ B_{j+1} $. Rozpatrzymy dwa przypadki:

    a) Jeśli $ 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 $ A_i $ i $ B_j $. Dlaczego? Gdyby w najdłuższym wspólnym podciągu $ A_{i+1} $ i $ B_{j+1} $ nie było literki $ x $ na końcu, moglibyśmy go przedłużyć, dokładając doń ostatnią literkę $ A_{i+1} $ i $ B_{j+1} $ (czyli właśnie tego $ x $). 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 $ A_{i+1} $ i $ B_{j+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.


Znaleziony LCS (kolor zielony) można przedłużyć o wspólną literkę 'r'

    b) Jeśli $ A[i+1]=x $ a $ B[j+1]=y $ i $ x\neq y $, to LCS dla $ A_{i+1} $ i $ B_{j+1} $ jest też LCS dla co najmniej jednej z dwóch par: $ A_{i} $ i $ B_{j+1} $ lub $ A_{i+1} $ i $ B_{j} $. Skąd taki wniosek? Ostatnią literką najdłuższego wspólnego podciągu dla $ A_{i+1} $ i $ B_{j+1} $ nie mogą być jednocześnie $ x $ i $ y $ (bo to dwie różne literki). Zatem jeden z wyrazów $ A_{i+1} $ i $ B_{j+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.


Najdłuższy wspólny podciąg dla "dolinie" i "jogini" jest jednocześnie najdłużym wspólnym podciągiem "dolini" oraz "jogini"

    Czyli możemy z pewnością stwierdzić, że $ LCS(i+1,j+1) $ (tak będziemy od teraz oznaczać długość LCS dla pary $ A_{i+1} $, $ B_{j+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] \neq B[j+1] $(przypadek b).

Obserwacja druga

    LCS dla $ A_0 $ i $ B_j $ zawsze składa się z zera literek. Jest to dość oczywiste - w $ A_0 $ nie ma żadnej literki, więc nic dłuższego niż słowo puste nie może być podciągiem $ A_0 $. Analogicznie: LCS dla $ A_i $ i $ B_0 $ 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 $

5
Twoja ocena: Brak Ocena: 5 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com