Rog ajutor!
Două șiruri distincte de caractere formează o pereche rezervă dacă unul dintre ele se poate obține din celălalt, prin împărțirea lui în două secvențe/subșiruri și apoi interschimbarea acestora.
Exemplu: oricare două dintre șirurile stea, aste, east, teas pot forma o pereche rezervă (dacă stea se împarte în st și ea se obține east, dacă se împarte în s și tea se obține teas etc.).
Subprogramul rezerva are doi parametri, s1 și s2, prin care primește câte un șir de cel mult 100 de caractere, numai litere mici ale alfabetului englez. Subprogramul returnează valoarea 1, dacă cele două șiruri formează o pereche rezervă, sau valoarea 0 în caz contrar.
Scrieți un program Pascal/C/C++ care citește de la tastatură un text format din maximum 100 de caractere, în care cuvintele sunt formate din litere mici ale alfabetului englez și sunt separate prin unul sau mai multe spații. Programul afișează pe ecran toate perechile rezervă formate din cuvinte din text. Fiecare pereche este afișată pe câte o linie a ecranului, între paranteze rotunde, iar cuvintele care o formează se afișează într-o ordine oarecare, separate prin caracterul #. Dacă nu există nicio astfel de pereche, se afișează pe ecran mesajul nu exista. Programul cuprinde definiția completă a subprogramului precizat mai sus, precum și apeluri utile ale acestuia.
Exemplu: dacă se citește textul
in aste nopti o stea numita seta ni se arata in est
se afișează pe ecran perechile de mai jos, nu neapărat în această ordine
(aste#stea) (in#ni)
Răspunsuri la întrebare
► COD C++ :
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_set>
//Functie suplimentara - returneaza urmatoarea permutare circulara a sirului transmis ca parametru
inline std::string genereaza_permutare_circulara(const std::string& s) {
return s[s.length() - 1] + s.substr(0, s.length()-1);
}
//Functie ceruta
bool rezerva(std::string s1, std::string s2) {
//Optimizare pentru performanta - daca sirurile au lungime diferita atunci nu pot alcatui pereche de rezerva
if (s1.length() != s2.length()) return false;
//Genereaza permutarile circulare ale lui s1 si compara-le cu s2
for (size_t id_permutare = 0; id_permutare < s1.length(); ++id_permutare) {
s1 = genereaza_permutare_circulara(s1);
if (s1 == s2) return true;
}
//Daca nu a fost gasit match atunci sirurile nu sunt perechi de rezerva
return false;
}
int main() {
std::string input, cuv_curent;
std::unordered_set<std::string> cuvinte;
bool exista_cel_putin_o_pereche = false;
//Citeste sir
std::getline(std::cin, input);
//Declara flux intrare cu continutul stringului input
std::stringstream ss(input);
//Cat timp avem chestii in stream
while (ss) {
//Citeste cuvant curent
ss >> cuv_curent;
//Daca cuvantul e deja in multime sari peste
if (cuvinte.find(cuv_curent) != cuvinte.end())
continue;
//Verifica match cu celelalte cuvinte anterioare din multime
for (std::string cuv_ante : cuvinte)
if (rezerva(cuv_curent, cuv_ante)) {
std::cout << "(" << cuv_ante << "#" << cuv_curent << ")";
exista_cel_putin_o_pereche = true;
}
//Adauga cuvantul in multime
cuvinte.insert(cuv_curent);
}
if (!exista_cel_putin_o_pereche) std::cout << "nu exista";
}
► Nota :
Am folosit elemente "moderne" de C++ (string, unordered_set, fluxuri). Daca ai nelamuriri cu privire la rezolvare te rog sa lasi comentariu pentru a le rezolva.
Am ales sa folosesc unordered_set in loc de vector pentru eficienta de cautare in O(1), in loc de O(n) - specifica vectorului nesortat.
Daca o permutare circulara a sirului s1 e identic cu sirul s2 atunci cele doua formeaza o pereche de rezerva.
