Advertisement
danielvitor23

Untitled

Mar 14th, 2020
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. // setLetrasFrase == setLetrasPalavras, setFrase != setPalavras
  10.  
  11. int tamText;
  12. string text; // Frase atual
  13. vector<string> wordsTot; //Palavras
  14. vector<string> words; //Palavras inseridas
  15. vector<string> res; //Final answer
  16. set<string> wordsText, wordsInsert; //Forbidden, insertedWords
  17.  
  18. vector<string> split(string s) {
  19. char c = ' ';
  20. vector<string> rr;
  21.  
  22. string buff{""};
  23.  
  24. for (int i = 0; i < s.size(); i++) {
  25. if (s[i] == ' ') {
  26. rr.push_back(buff);
  27. buff.clear();
  28. } else if (s[i] >= 'A' && s[i] <= 'Z') {
  29. buff += s[i];
  30. }
  31. }
  32.  
  33. if (!buff.empty()) rr.push_back(buff);
  34.  
  35. return rr;
  36. } //Complete
  37.  
  38. int trimSize(string s) {
  39. int cc = 0;
  40. for (char c : s) {
  41. if (c >= 'A' && c <= 'Z') cc++;
  42. }
  43. return cc;
  44. }
  45.  
  46. bool checkAnagram(string textT, vector<string> wordsTest) {
  47. int a[26], b[26];
  48. memset(a, 0, sizeof(a));
  49. memset(b, 0, sizeof(b));
  50.  
  51. for (char c : textT) {
  52. if (c >= 'A' && c <= 'Z') a[c - 'A']++;
  53. }
  54.  
  55. for (string str : wordsTest)
  56. for (char c : str)
  57. b[c - 'A']++;
  58.  
  59. for (int i = 0; i < 26; i++)
  60. if (a[i] != b[i]) return false;
  61.  
  62. return true;
  63. } //Complete
  64.  
  65. void backtrack(int id, int cnt) {
  66. if (id > wordsTot.size() || cnt > tamText) return;
  67. if (cnt == tamText && wordsText != wordsInsert && checkAnagram(text, words)) {
  68. string s;
  69. for (string t : words) {
  70. s.append(" " + t);
  71. }
  72. res.push_back(text + " =" + s);
  73. return;
  74. }
  75.  
  76. backtrack(id+1, cnt);
  77.  
  78. words.push_back(wordsTot[id]);
  79. wordsInsert.insert(wordsTot[id]);
  80. backtrack(id+1, cnt + wordsTot[id].size());
  81. words.pop_back();
  82. wordsInsert.erase(wordsTot[id]);
  83. }
  84.  
  85. int main() {
  86. //cin.tie(NULL);
  87. //ios_base::sync_with_stdio(false);
  88. string s = "";
  89.  
  90. while(true) {
  91. cin >> s;
  92. if (s == "#") break;
  93. wordsTot.push_back(s);
  94. }
  95.  
  96. getchar();
  97. s = "";
  98. while(true) {
  99. getline(cin, s);
  100. if (s == "#") break;
  101.  
  102. wordsText.clear();
  103. wordsInsert.clear();
  104. tamText = trimSize(s);
  105. text = s;
  106. for (string t : split(text)) {
  107. wordsText.insert(t);
  108. }
  109. backtrack(0, 0);
  110. }
  111.  
  112. sort(res.begin(), res.end());
  113. for (string s : res) {
  114. cout << s << "\n";
  115. }
  116.  
  117. return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement