Question

Salut, am o problema cu codul de mai jos care acopera 9 din 10 cazuri si nu imi pot da seama care este ultimul caz pe care nu il acopera.

Cerinta :
Marcel și Marius au de dat un test la literatură și vor să colaboreze pentru a crea o compunere cât mai complexă. Totuși, această practică nu e agreată de profesoara lor, care de fiecare dată când găsește 2 lucrări similare le verifică atent, să nu conțină secvențe prea lungi de text care coincid.

După ce a învățat programare, Marcel a descoperit că poate introduce compunerea lui și a lui Marius într-un program pe calculator, iar acel program îi va spune care e cel mai lung șir de caractere care se găsește ca subsecvență în ambele compuneri. O subsecvență a unui șir s e un șir de caractere care apar pe poziții consecutive în s.

Marcel a scris repede programul său, iar acum se simte pregătit pentru următorul test. Poți să scrii un program care rezolvă problema la fel de repede?

Date de intrare
Programul citește de la tastatură, de pe prima linie, șirul de caractere s1, reprezentând compunerea lui Marcel. De pe a doua linie se va citi șirul s2, reprezentând compunerea lui Marius.

Date de ieșire
Programul va afișa pe ecran un șir de caractere care apare ca subsecvență în ambele compuneri și are lungime maximă. Dacă sunt mai multe astfel de șiruri, se va afișa cel care începe pe poziția cea mai din stânga din primul șir.

Restricții și precizări
sirurile s1 și s2 vor avea cel mult 1000 de caractere și vor fi formate din litere ale alfabetului englez și spații.
Caracterele din secvența comună găsită trebuie să coincidă cu exactitate (c != C)

Codul meu este urmatorul :

#include
#include
using namespace std;

int main() {
char s1[1001], s2[1001];
cin.getline(s1, 1001);
cin.getline(s2, 1001);
int n1 = strlen(s1);
int n2 = strlen(s2);
int max_len = 0, max_start = 0, max_end = 0, curr_len = 0, curr_start = 0, curr_end = 0;
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
if (s1[i] == s2[j]) {
curr_len = 1;
curr_start = i;
curr_end = i;
while (curr_end + 1 < n1 && j + curr_len < n2 && s1[curr_end + 1] == s2[j + curr_len]) {
++curr_len;
++curr_end;
}
if (curr_len > max_len) {
max_len = curr_len;
max_start = curr_start;
max_end = curr_end;
}
}
}
}
for (int i = max_start; i <= max_end; ++i) {
cout << s1[i];
}
cout << endl;
return 0;
}

Answer 1

Răspuns:

Dupa bucla for te rog sa pui:

if (max_len == 0) {

cout << "Nu exista subsecvente comune.\n";

} else {

for (int i = max_start; i <= max_end; ++i) {

cout << s1[i];

}

cout << endl;

}