Największy wspólny podciąg - c++
Ostatnio zmodyfikowano 2016-11-11 19:46
mjmjmjj Temat założony przez niniejszego użytkownika |
Największy wspólny podciąg - c++ » 2016-11-11 16:15:14 Witam, mam problem z pewnym zadaniem. Mianowicie, chodzi o odnalezienie największego wspólnego podciągu dwóch ciągów. Oto treść:
Limit pamięci: 64 MB Dane są dwa ciągi znaków X i Y , składające się z liter 'a','b' i 'c'. Należy znaleźć najdłuższy niemalejący wspólny podciąg ciągów X i Y. Inaczej mówiąc, należy znaleźć najdłuższy ciąg, który: jest podciągiem ciągów X i Y , czyli da się go otrzymać przez usunięcie pewnych liter z ciągów X i Y ; jest niemalejący pod względem kolejności liter w alfabecie, czyli przed wystąpieniem litery ,,c"nie wystąpi litera o większym kodzie ASCII niż ,,c" .
Wejście: W pierwszej linii znajdują się dwie liczby całkowite n i m, oznaczające długości ciągów X i Y . W drugiej linii znajduje się ciąg X , a w następnej Y .
Wyjście: W pierwszym wierszu należy wypisać długość najdłuższego ciągu spełniającego warunki zadania. Przykład: Dla danych wejściowych: 5 6 cabbc bacbcc poprawną odpowiedzią jest: 3 Wyjaśnienie: Najdłuższy ciąg spełniający warunki zadania to "abc".
Generalnie, rozumiem o co chodzi w tym zadaniu, jednak nie do końca wiem, jak to dobrze napisać (moja przygoda z C++ trwa 2 miesiące)
Na razie mam coś takiego:
#include <iostream> #include <algorithm> using namespace std; main () { int k, l; cin>>k>>l; char C[k]; char C[l]; for (int i=0; i<k; i++) { C[0] =0; for (int j=0; j<l; j++) C[0][j] =0; } for (int i=1; i<k; i++) { for (int j=1; j<l; j++) if A = B[j] C[j] = C[i-1][j-1] + 1 else C[j] = max(C[i-1][j], C[j-1]); } return 0; }
I nie wiem, jak wpisać i wypisać dobrze zmienne i tablice. Jeżeli to się komuś wydaje żałosne, to przepraszam, jednak naprawdę nie wiem o co chodzi. Będę wdzięczny za każdą pomoc. |
|
mateczek |
» 2016-11-11 19:46:55 weź edytuj post. I jeszcze raz wklej kod w znaczniki [cpp] //tutaj kod[/cpp] |
|
« 1 » |