Witam,
otóż mam za zadanie znaleźć ilość najdłuższych wspólnych podciągów dwóch wyrazów (nie długość!). Nie za bardzo wiem, jak się za to zabrać. Umiem obliczyć długość najdłuższego wspólnego podciągu, ilość wspólnych podciągów, aczkolwiek ilość najdłuższych wspólnych podciągów już nie.
np. dla wyrazów abba i abab najdłuższymi wspólnymi podciągami są słowa abb i aba, a więc wynik to 2, bo są dwa najdłuższe podciągi.
Ma ktoś może jakiś pomysł, jak możnaby wykonać to zadanie i chciałby służyć pomocą?
0
0
Przeciez to jest tylko modyfikacja znajdowania LCS przez dynamiczne programowanie. W fazie odtwarzania rozwiazania na podstawie dlugosci (czyli faza traceback) masz wiele mozliwosci - wystarczy sprawdzic je wszystkie i policzyc ile tego wyszlo.