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ą?
- Rejestracja:ponad 8 lat
- Ostatnio:prawie 6 lat
- Postów:6
0
C++ - Rejestracja:prawie 14 lat
- Ostatnio:około 8 lat
- Postów:1176
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.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.