Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

    Teraz zajmiemy się dalszym uzupełnianiem tabeli. Będziemy wyliczać wartości w kolejnych wierszach, idąc od lewej do prawej. Dzięki temu w chwili, gdy przyjdzie nam ustalać wartość w komórce $ (i,j) $, wszystkie potrzebne nam do tego komórki będą już poprawnie wypełnione. Z obserwacji pierwszej wynika bowiem, że wartość w $ (i,j) $ zależeć może jedynie od trzech komórek: $ (i-1,j-1) $, $ (i,j-1) $, $ (i-1,j) $.


W takiej kolejności będziemy wypełniać komórki tablicy.

    Jak wyliczamy wartość w polu $ (i,j) $? Jeśli $ A[i]=B[j] $, to zgodnie ze wzorem z obserwacji pierszej musimy dodać jeden do $ (i-1,j-1) $. Jeśli jednak $ A[i] \neq B[j] $, to w $ (i,j) $ wpisujemy większą z liczb znajdujących się w komórkach $ (i-1,j) $ i $ (i,j-1) $.


Jeśli piąta literka jednego słowa zgadza się z czwartą literką drugiego, to dodajemy jeden do wartości z pola na skos.

Jeśli są to różne literki, to w polu ze znakiem zapytania wpisujemy większą z liczb $ k $ i $ m $, czyli większą z wartości z pól sąsiadujących z danym polem z lewej strony i z góry.

    Wypełniamy w ten sposób całą tablicę i w polu $ (n,m) $ otrzymujemy długość najdłuższego wspólnego podciągu dla wyrazów $ A $ i $ B $. Jeśli interesowała nas jedynie ta wartość, to możemy zakończyć pracę. Coż jednak mamy zrobić, jeśli nie chcemy znać tylko długości LCS dla tych wyrazów, ale także i to, jaką ten podciąg ma postać? Na szczęście z łatwością możemy odtworzyć jego wygląd, wszystko dzięki wypełnionej już tablicy!

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com