Advertisement
nicuvlad76

Untitled

Jan 21st, 2021
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.62 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <string>
  4. #include <string.h>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. #define N_MAX 6
  11. #define M_MAX 6
  12. #define C_MAX 200
  13. #define A_SIZE 26 // alphabet size
  14.  
  15. char tab[N_MAX][C_MAX];
  16. int N, M, C;
  17.  
  18. struct TrieNode {
  19. // chs: cele 26 de litere din alfabet
  20. TrieNode* chs[A_SIZE];
  21. // count: informatie despre cuvantul de la radcina pana la nod
  22. // -1 cuvantul *nu* e in dictionar
  23. // 0 cuvantul e in dictionar
  24. // > 0 cuvantul e in dictionar si apare de count ori
  25. int count;
  26.  
  27. TrieNode() {
  28. count = -1;
  29. memset(chs, 0, A_SIZE * sizeof(struct TrieNode*));
  30. }
  31.  
  32. void insert(string cuv);
  33. void print_and_collect(fstream &fout, string cuv, int min_count, vector<int> &counts);
  34. void count_words(int& n_cuv, int min_count);
  35. };
  36.  
  37. void TrieNode::insert(string cuv) {
  38. TrieNode* tn = this;
  39. int clen = cuv.length();
  40. for (int i = 0; i < clen; i++) {
  41. int idx = cuv[i] - 'a';
  42. if (tn->chs[idx] == NULL ) {
  43. tn->chs[idx] = new TrieNode();
  44. }
  45. tn = tn->chs[idx];
  46. }
  47. // ultima litera din cuvant
  48. tn->count = 0;
  49. }
  50.  
  51. void TrieNode::count_words(int& n_cuv, int min_count) {
  52. TrieNode* tn = this;
  53. if (tn == NULL)
  54. return;
  55.  
  56. if (tn->count >= min_count) {
  57. n_cuv = n_cuv + 1;
  58. }
  59.  
  60. for(int i = 0; i < A_SIZE; i++) {
  61. tn->chs[i]->count_words(n_cuv, min_count);
  62. }
  63. }
  64.  
  65. void TrieNode::print_and_collect(fstream &fout, string cuv, int min_count, vector<int> &counts) {
  66. TrieNode* tn = this;
  67. if (tn == NULL)
  68. return;
  69. if (tn->count >= min_count) {
  70. fout << cuv << " " << tn->count << "\n";
  71. counts.push_back(tn->count);
  72. }
  73. for(int i = 0; i < A_SIZE; i++) {
  74. cuv.push_back('a' + i);
  75. tn->chs[i]->print_and_collect(fout, cuv, min_count, counts);
  76. cuv.erase(cuv.end() - 1, cuv.end());
  77. }
  78. }
  79.  
  80. void print_solution(fstream &fout, TrieNode &dict, int min_count) {
  81. string s;
  82. vector<int> counts;
  83. int n_words = 0;
  84. dict.count_words(n_words, min_count);
  85. fout << n_words << "\n";
  86.  
  87. dict.print_and_collect(fout, s, min_count, counts);
  88.  
  89. vector<int>::iterator it;
  90. for(it = counts.begin(); it != counts.end(); it++) {
  91. fout << (char)('a' + (*it % 26)) ;
  92. }
  93. fout << "\n";
  94. }
  95.  
  96. bool in_bounds(int x, int y) {
  97. return (x >= 0 && y >= 0 && x < N && y < M);
  98. }
  99.  
  100. void dfs(TrieNode *dict, int i, int j) {
  101. int idx_l = tab[i][j] - 'a';
  102. int idx_r = tab[i][j] - 'a' + 1;
  103. if (tab[i][j] == '?') {
  104. idx_l = 0;
  105. idx_r = A_SIZE;
  106. }
  107.  
  108. int old_ij = tab[i][j];
  109. for(int idx = idx_l; idx < idx_r; idx ++ ) {
  110. tab[i][j] = 'a' + idx;
  111.  
  112. TrieNode* cur_tn = dict->chs[idx];
  113. if(cur_tn == NULL)
  114. continue;
  115.  
  116. // increase current word
  117. if(cur_tn->count >= 0) {
  118. cur_tn->count++;
  119. }
  120.  
  121. for(int dx = -1; dx < 2; dx++){
  122. for(int dy = -1; dy < 2; dy++){
  123. if((dx == 0 && dy == 0) || !in_bounds(i + dx, j + dy))
  124. continue;
  125.  
  126. dfs(cur_tn, i + dx, j + dy);
  127. }
  128. }
  129. }
  130. tab[i][j] = old_ij;
  131. }
  132.  
  133. int main() {
  134. int i, j;
  135. fstream fin, fout;
  136. fin.open("cuvinteascunse.in", fstream::in);
  137. fout.open("cuvinteascunse.out", fstream::out);
  138. fin >> N >> M >> C;
  139. for(i = 0; i < N; i++)
  140. for(j = 0; j < M; j++)
  141. fin >> tab[i][j];
  142.  
  143. TrieNode dict;
  144. string cuv;
  145. for(i = 0; i < C; i++){
  146. fin >> cuv;
  147. std::transform(cuv.begin(), cuv.end(),cuv.begin(), ::tolower);
  148. dict.insert(cuv);
  149. }
  150.  
  151. for(i = 0; i < N; i++)
  152. for(j = 0; j < M; j++)
  153. dfs(&dict, i, j);
  154.  
  155. print_solution(fout, dict, 1);
  156.  
  157. fin.close();
  158. fout.close();
  159. return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement