daily pastebin goal
41%
SHARE
TWEET

subsecvente2

a guest Feb 13th, 2018 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define NMAX 50005
  3.  
  4. using namespace std;
  5. ifstream fin("subsecvente2.in");
  6. ofstream fout("subsecvente2.out");
  7.  
  8. struct TRIE{
  9.     int nd;
  10.     TRIE *son[2];
  11.     TRIE()
  12.     {
  13.         nd = 1;
  14.         memset(son, 0, sizeof(son));
  15.     }
  16. };
  17.  
  18. void add_word(TRIE *nod, char cuv[], int poz, int dim)
  19. {
  20.     if (cuv[poz] == '\0' || dim == 61)
  21.         return;
  22.     int nxt = cuv[poz] - 'a';
  23.     if (nod -> son[nxt] == 0)
  24.         nod -> son[nxt] = new TRIE();
  25.     add_word(nod -> son[nxt], cuv, poz + 1, dim + 1);
  26. }
  27.  
  28. int N, mx;
  29.  
  30. void search_word(TRIE *nod, char cuv[], int poz, int dim, int act)
  31. {
  32.     if (nod -> nd == act - 1) nod -> nd = act;
  33.     if (nod -> nd == N) mx = max(mx, dim);
  34.     if (cuv[poz] == '\0' || dim == 61)
  35.         return;
  36.     int nxt = cuv[poz] - 'a';
  37.     if (nod -> son[nxt] != 0 && nod -> son[nxt] -> nd >= act-1 )
  38.         search_word(nod -> son[nxt], cuv, poz + 1, dim + 1, act);
  39. }
  40.  
  41. char cuv[NMAX];
  42. TRIE *ROOT = new TRIE();
  43.  
  44. int main()
  45. {
  46.     fin >> N;
  47.     for (int i = 1; i <= N; i++)
  48.     {
  49.         fin >> cuv;
  50.         int L = strlen(cuv);
  51.         for (int j = 0; j < L; j++)
  52.         {
  53.             if (i == 1)
  54.                 add_word(ROOT, cuv, j, 0);
  55.             else search_word(ROOT, cuv, j, 0, i);
  56.         }
  57.     }
  58.     fout << mx << "\n";
  59.     fin.close();
  60.     fout.close();
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top