#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";
}
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.
