Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Największy wspólny podciąg - c++

Ostatnio zmodyfikowano 2016-11-11 19:46
Autor Wiadomość
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.
P-153560
mateczek
» 2016-11-11 19:46:55
weź edytuj post. I jeszcze raz wklej kod w znaczniki
[cpp] //tutaj kod[/cpp]
P-153579
« 1 »
  Strona 1 z 1