Advertisement
Manioc

portunhol

Jul 2nd, 2019
268
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. struct node{
  7.     struct node* word[26];
  8.     bool end;
  9.  
  10.     ~node(){
  11.         delete[] word;
  12.     }
  13. };
  14.  
  15. node *p, *s;
  16.  
  17. int add(string &s, node* root){
  18.     node* current = root;
  19.  
  20.     int ans = 0;
  21.     for(int i = 0; i < s.size(); i++){
  22.         int letter = s[i]-'a';
  23.  
  24.         if(current->word[letter] == NULL) {
  25.             ans++;
  26.             current->word[letter] = new node();
  27.         }
  28.         //cout << "ola\n";
  29.         current = current->word[letter];
  30.     }
  31.     current->end = true;
  32.  
  33.     return ans;
  34. }
  35.  
  36. ll prefixos, cutl[26];
  37. void cut(node* no, int h){
  38.     for(int i = 0; i < 26; i++){
  39.         if(no->word[i] == NULL) continue;
  40.  
  41.         if(h) cutl[i]++;
  42.         cut(no->word[i], h + 1);
  43.     }
  44. }
  45.  
  46. ll solve(node* no, int h){
  47.  
  48.     ll ans = 0;
  49.     if(h) ans = prefixos;
  50.     for(int i = 0; i < 26; i++){
  51.         if(no->word[i] == NULL) continue;
  52.  
  53.         if(h) ans -= cutl[i];
  54.         ans += solve(no->word[i], h + 1);
  55.     }
  56.  
  57.     return ans;
  58. }
  59. int main(){
  60.     ios::sync_with_stdio(false);
  61.     cin.tie(NULL);
  62.     while(true){
  63.         int qp, qe; cin >> qp >> qe;
  64.         if((qp+qe) == 0) break;
  65.         s = new node();
  66.         p = new node();
  67.  
  68.         prefixos = 0;
  69.         memset(cutl, 0, sizeof cutl);
  70.         for(int i = 0; i < qp; i++){
  71.             string aux; cin >> aux;
  72.             prefixos += add(aux, p);
  73.         }
  74.  
  75.         for(int i = 0; i < qe; i++){
  76.             string aux; cin >> aux;
  77.             reverse(aux.begin(), aux.end());
  78.             add(aux, s);
  79.         }
  80.  
  81.         cut(p, 0);
  82.         cout << solve(s, 0) << endl;
  83.         //delete s;
  84.         //delete p;
  85.     }
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement