Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #include <set>
- using namespace std;
- // setLetrasFrase == setLetrasPalavras, setFrase != setPalavras
- int tamText;
- string text; // Frase atual
- vector<string> wordsTot; //Palavras
- vector<string> words; //Palavras inseridas
- vector<string> res; //Final answer
- set<string> wordsText, wordsInsert; //Forbidden, insertedWords
- vector<string> split(string s) {
- char c = ' ';
- vector<string> rr;
- string buff{""};
- for (int i = 0; i < s.size(); i++) {
- if (s[i] == ' ') {
- rr.push_back(buff);
- buff.clear();
- } else if (s[i] >= 'A' && s[i] <= 'Z') {
- buff += s[i];
- }
- }
- if (!buff.empty()) rr.push_back(buff);
- return rr;
- } //Complete
- int trimSize(string s) {
- int cc = 0;
- for (char c : s) {
- if (c >= 'A' && c <= 'Z') cc++;
- }
- return cc;
- }
- bool checkAnagram(string textT, vector<string> wordsTest) {
- int a[26], b[26];
- memset(a, 0, sizeof(a));
- memset(b, 0, sizeof(b));
- for (char c : textT) {
- if (c >= 'A' && c <= 'Z') a[c - 'A']++;
- }
- for (string str : wordsTest)
- for (char c : str)
- b[c - 'A']++;
- for (int i = 0; i < 26; i++)
- if (a[i] != b[i]) return false;
- return true;
- } //Complete
- void backtrack(int id, int cnt) {
- if (id > wordsTot.size() || cnt > tamText) return;
- if (cnt == tamText && wordsText != wordsInsert && checkAnagram(text, words)) {
- string s;
- for (string t : words) {
- s.append(" " + t);
- }
- res.push_back(text + " =" + s);
- return;
- }
- backtrack(id+1, cnt);
- words.push_back(wordsTot[id]);
- wordsInsert.insert(wordsTot[id]);
- backtrack(id+1, cnt + wordsTot[id].size());
- words.pop_back();
- wordsInsert.erase(wordsTot[id]);
- }
- int main() {
- //cin.tie(NULL);
- //ios_base::sync_with_stdio(false);
- string s = "";
- while(true) {
- cin >> s;
- if (s == "#") break;
- wordsTot.push_back(s);
- }
- getchar();
- s = "";
- while(true) {
- getline(cin, s);
- if (s == "#") break;
- wordsText.clear();
- wordsInsert.clear();
- tamText = trimSize(s);
- text = s;
- for (string t : split(text)) {
- wordsText.insert(t);
- }
- backtrack(0, 0);
- }
- sort(res.begin(), res.end());
- for (string s : res) {
- cout << s << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement