Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Algorytm

    Jeśli poniższy opis wyda ci się niejasny, możesz spojrzeć na szóstą stronę tego tekstu, gdzie znajduje się przykład działania algorytmu na dwóch konkretnych wyrazach.

    Jeśli liczby $ n $ i $ m $ są długościami odpowiednio $ A $ i $ B $, to z pewnością $ A_n = A $ i $ B_m = B $. Wtedy $ LCS(n,m) $ oznacza długość najdłuższego wspólnego podciągu dla całych wyrazów $ A $ i $ B $. Aby wyliczyć tę wartość, utworzymy tablicę o wymiarach $ n+1 $ na $ m+1 $ komórek, bowiem w komórce $ (i,j) $ chcemy przechowywać liczbę $ LCS(i,j) $ (dla $ i \in \{0,1, \ldots, n\} $ oraz $ j \in \{0,1, \ldots, m\} $). Druga obserwacja pozwoli nam na wpisanie do tej tablicy pewnej liczby początkowych wartości, wzór z obserwacji pierwszej posłuży do dalszego wypełniania komórek.


Przykładowa tablica, która może posłużyć do wyznaczenia LCS dla dwóch słów o długości $ 8 $.

    Skoro prawdą jest, że $ LCS(i,0) = 0 $ i $ LCS(0,j) = 0 $, to zerowy wiersz i zerową kolumnę tabeli wypełnić należy zerami.


Wpisujemy zera.
5
Twoja ocena: Brak Ocena: 5 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com