Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Odtwarzamy wygląd LCS

    Wyobraźmy sobie, że w każdej komórce $ (i,j) $ tablicy poza liczbą znajduje się też i strzałka, która wskazuje na pole zawierające tę wartość, która była nam potrzebna przy wyliczaniu liczby w $ (i,j) $. Zauważmy, że jeśli $ A[i]=B[j] $ to strzałka w $ (i,j) $ będzie skierowana na skos, a jeśli $ A[i] \neq B[j] $, to w górę lub w lewo - zależnie od tego, gdzie będzie większa wartość (w przypadku remisu kierunek strzałki jest dowolny).

    Strzałka skośna odpowiada "przedłużaniu" LCS o ostatnią literkę obu rozpatrywanych prefiksów (przypadek "a" z obserwacji pierwszej).

    Strzałki w lewo i w górę odpowiadają następującej decyzji: czy dłuższym podciągiem $ A_{i+1} $ i $ B_{j+1} $ będzie LCS $ A_i $ i $ B_{j+1} $, czy może LCS $ A_{i+1} $ i $ B_{j} $?


Przykładowe rozmieszczenie strzałek.

    Aby odtworzyć LCS musimy przejść zgodnie ze strzałkami z pola $ (n,m) $ do lewej bądź górnej krawędzi tablicy. Za każdym razem, gdy pójdziemy na skos, znajdujemy kolejną literkę z LCS. W związku z tym, że cała tablica jest już wypełniona wartościami $ LCS(i,j) $, strzałki wskazują zawsze ten wybór, który prowadzi do najdłuższego podciągu. Jeśli więc natrafimy na strzałkę skośną w polu $ (k,l) $, oznacza to, że najlepiej będzie jako kolejną literkę odtwarzanego LCS wybrać $ A[k] = x $ (zachodzi też $ x = B[l] $, bo tylko w takiej sytuacji mogliśmy natrafić na strzałkę na skos). Pamiętajmy jednak, że odtwarzamy LCS od końca!


Na czerwono zaznaczona jest droga do krawędzi wyznaczona przez strzałki.

    Oczywiście nie musimy uwzględniać żadnych strzałek w naszym kodzie. Wystarczy bowiem kilka porównań, aby sprawdzić w którą stroną skierowana by była strzałka w danym polu. Jeśli $ A[i]=B[j] $, to w polu $ (i,j) $ znajdowałaby się strzałka na skos. W przeciwnym wypadku musimy sprawdzić w którym z pól $ (i-1,j) $ czy $ (i,j-1) $ wpisana jest większa wartość - na to pole wskazywałaby strzałka z komórki $ (i,j) $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com