Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

    Algorytm, który wyznacza najdłuższy wspólny podciąg (z ang. LCS - Longest Common Subsequence) dwóch wyrazów, jest eleganckim przykładem potęgi programowania dynamicznego. Rozwiązanie konstruowane jest stopniowo - zaczynamy od mniejszych (zatem łatwiejszych) podproblemów. Wyniki dla nich pozwolą nam na zgrabne utworzenie odpowiedzi dla pierwotnego zadania.

    Jeśli jakieś pojęcia w tym tekście wydadzą ci się niejasne, zawsze możesz zajrzeć do artykułu o podstawach algorytmów tekstowych.

Definicja problemu

    Przez większość tego tekstu będziemy starali się rozwiązać jeden problem, wypada zatem opisać go w ścisły i jednoznaczny sposób. Aby to uczynić wprowadźmy najpierw następujące pojęcie:

   Niech $ A $ i $ B $ będą dwoma wyrazami (czyli ciągami liter, zakładamy to dla wygody - w rzeczywistości mogą to być dowolne ciągi). Mówimy, że $ A $ jest podciągiem $ B $ wtedy i tylko wtedy, gdy istnieje taki rosnący ciąg liczb naturalnych $ x_i $, że zachodzi:

$ A[i] = B[x_i] $ dla wszystkich $ i = 1 \ldots n $, gdzie $ n $ to długość wyrazu $ A $, a $ A[i] $ oznacza i-tą literkę z $ A $.

    Czyli, w prostszych słowach, $ A $ jest podciągiem $ B $, jeśli potrafimy tak wybierać z $ B $ kolejne literki, aby utworzyć wyraz $ A $.


Wyraz "mister" jest podciągiem wyrazu "marcinjestsuper"

    Teraz możemy w końcu zdefiniować problem przewodni tego artykułu:

   Dla danych dwóch wyrazów $ W_1 $ i $ W_2 $ należy znaleźć najdłuższy taki wyraz $ P $, aby $ P $ był podciągiem $ W_1 $ i podciągiem $ W_2 $.


Wyraz "KREA" jest najdłuższym wspólnym podciągiem "KARUZELA" i "KURIERA".
5
Twoja ocena: Brak Ocena: 5 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com