Najdłuższy wspólny podciąg
02.10.2010 - Marcin Oczeretko
RozwiązanieZdefiniujmy najpierw jeszcze jedno pomocnicze pojęcie: Niech będzie wyrazem złożonym z pierwszych liter . nazywamy prefiksem słowa . 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 pierwszaZałóżmy, że znamy długość najdłuższego wspólnego podciągu dla par prefiksów:
Na podstawie powyższych informacji spróbujemy teraz wyliczyć długość LCS dla i . Rozpatrzymy dwa przypadki: a) Jeśli i to LCS dla tych dwóch wyrazów może zostać utworzony poprzez dodanie literki na koniec LCS dla wyrazów i . Dlaczego? Gdyby w najdłuższym wspólnym podciągu i nie było literki na końcu, moglibyśmy go przedłużyć, dokładając doń ostatnią literkę i (czyli właśnie tego ). Ale wtedy powstałby podciąg dłuższy od najdłuższego! Literka musi być więc ostatnią literką każdego poprawnie wyliczonego LCS. Najmniej "utracimy" zatem jeśli źródłem literki będą końce i - pozostanie wtenczas jeszcze literek prefiksu i literek prefiksu 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 , to LCS dla i jest też LCS dla co najmniej jednej z dwóch par: i lub i . Skąd taki wniosek? Ostatnią literką najdłuższego wspólnego podciągu dla i nie mogą być jednocześnie i (bo to dwie różne literki). Zatem jeden z wyrazów i 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 (tak będziemy od teraz oznaczać długość LCS dla pary , ) to:
Obserwacja drugaLCS dla i zawsze składa się z zera literek. Jest to dość oczywiste - w nie ma żadnej literki, więc nic dłuższego niż słowo puste nie może być podciągiem . Analogicznie: LCS dla i też ma zawsze zero literek. Prawdziwe są zatem następujące równości:
dla każdego naturalnego (10 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com