Najdłuższy wspólny podciąg
02.10.2010 - Marcin Oczeretko
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 problemuPrzez 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 i 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 jest podciągiem wtedy i tylko wtedy, gdy istnieje taki rosnący ciąg liczb naturalnych , że zachodzi: dla wszystkich , gdzie to długość wyrazu , a oznacza i-tą literkę z . Czyli, w prostszych słowach, jest podciągiem , jeśli potrafimy tak wybierać z kolejne literki, aby utworzyć wyraz . 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 i należy znaleźć najdłuższy taki wyraz , aby był podciągiem i podciągiem . Wyraz "KREA" jest najdłuższym wspólnym podciągiem "KARUZELA" i "KURIERA".
(10 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com