Advertisement
Josif_tepe

Untitled

Jun 6th, 2023
793
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int ALPHABET_SIZE = 2;
  5. struct node {
  6.     node *children_of_this_node[ALPHABET_SIZE];
  7.     bool end_of_word;
  8.    
  9.     node() {
  10.         for(int i = 0; i < ALPHABET_SIZE; i++) {
  11.             children_of_this_node[i] = NULL;
  12.         }
  13.         end_of_word = false;
  14.     }
  15. };
  16. void insert_word(node * trie, string & s) {
  17.     node * tmp = trie;
  18.     for(int i = 0; i < (int) s.size(); i++) {
  19.         int current_char = s[i] - 'a';
  20.         if(tmp -> children_of_this_node[current_char] == NULL) {
  21.             tmp -> children_of_this_node[current_char] = new node();
  22.         }
  23.         tmp = tmp -> children_of_this_node[current_char];
  24.     }
  25.     tmp -> end_of_word = true;
  26. }
  27. bool search_word(node * trie, string & s) {
  28.     node * tmp = trie;
  29.     for(int i = 0; i < (int) s.size(); i++) {
  30.         int current_char = s[i] - 'a';
  31.         if(tmp -> children_of_this_node[current_char] == NULL) {
  32.             return false;
  33.         }
  34.         tmp = tmp -> children_of_this_node[current_char];
  35.     }
  36.     return tmp -> end_of_word;
  37. }
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     int n;
  41.     cin >> n;
  42.     vector<string> v(n);
  43.     for(int i = 0; i < n; i++) {
  44.         cin >> v[i];
  45.     }
  46.     for(int i = 0; i < n; i++) {
  47.         for(int j = i + 1; j < n; j++) {
  48.             if((int) v[i].size() < (int) v[j].size()) {
  49.                 swap(v[i], v[j]);
  50.             }
  51.         }
  52.     }
  53.     node * tries[n - 1];
  54.     for(int i = 0; i < n - 1; i++){
  55.         tries[i] = new node();
  56.     }
  57.     for(int at = 1; at < n; at++) {
  58.         for(int i = 0; i < (int) v[at].size(); i++) {
  59.             string tmp = "";
  60.             for(int j = i; j < min((int) i + 60, (int) v[at].size()); j++) {
  61.                 tmp += v[at][j];
  62.                 insert_word(tries[at - 1], tmp);
  63.             }
  64.         }
  65.     }
  66.     int result = 0;
  67.     for(int i = 0; i < (int) v[0].size(); i++) {
  68.         string tmp = "";
  69.         for(int j = i; j < min(i + 60, (int) v[0].size()); j++) {
  70.             tmp += v[0][j];
  71.             bool ok = true;
  72.             for(int k = 0; k < n - 1; k++) {
  73.            
  74.                 if(!search_word(tries[k], tmp)) {
  75.                     ok = false;
  76.                     break;
  77.                 }
  78.             }
  79.             if(ok) {
  80.                 result = max(result, (int) tmp.size());
  81.             }
  82.         }
  83.     }
  84.     cout << result << endl;
  85.     return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement