Advertisement
K_Y_M_bl_C

Untitled

Dec 21st, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #ifdef _DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #include <bits/stdc++.h>
  6.    
  7. using namespace std;
  8.    
  9. typedef long long ll;
  10. typedef vector<ll> vll;
  11. typedef pair<int, int> pii;
  12. typedef vector<int> vi;
  13. typedef long double ld;
  14.    
  15. #define mk make_pair
  16. #define inb push_back
  17. #define enb emplace_back
  18. #define X first
  19. #define Y second
  20. #define all(v) v.begin(), v.end()
  21. #define sqr(x) (x) * (x)
  22. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  23. #define y1 AYDARBOG
  24. //continue break pop_back return
  25.    
  26. int solve();
  27.    
  28. int main()
  29. {
  30.     //ios_base::sync_with_stdio(0);
  31.     //cin.tie(0);
  32. #define TASK "search5"
  33. #ifndef _DEBUG
  34.     freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  35. #endif
  36.     solve();
  37. #ifdef _DEBUG
  38.     fprintf(stderr, "\nTIME: %.3f\n", TIME);
  39. #endif
  40. }
  41.    
  42. const int BUFSZ = (int)1e6 + 7;
  43. char buf[BUFSZ];
  44. string get_str()
  45. {
  46.     scanf(" %s", buf);
  47.     return string(buf);
  48. }
  49.  
  50. struct Trie
  51. {
  52.     struct Node
  53.     {
  54.         int cnt;
  55.         int suf;
  56.         vi go;
  57.         Node() { cnt = 0, suf = 0, go.assign(26, -1); };
  58.     };
  59.     vector<Node> t;
  60.     vector<vi> g;
  61.     vll dp;
  62.     Trie() { t.inb(Node()); };
  63.     int adds(string s)
  64.     {
  65.         int u = 0;
  66.         for (int i = 0; i < (int)s.size(); ++i)
  67.         {
  68.             if (t[u].go[s[i] - 'a'] == -1)
  69.             {
  70.                 t[u].go[s[i] - 'a'] = t.size();
  71.                 t.inb(Node());
  72.             }
  73.             u = t[u].go[s[i] - 'a'];
  74.         }
  75.         return u;
  76.     }
  77.     void buildAK()
  78.     {
  79.         g.resize(t.size());
  80.         dp.assign(t.size(), -1);
  81.         queue<int> q;
  82.         q.push(0);
  83.         while (!q.empty())
  84.         {
  85.             int u = q.front();
  86.             q.pop();
  87.             g[t[u].suf].inb(u);
  88.             for (int i = 0; i < 26; ++i)
  89.             {
  90.                 int to = 0;
  91.                 if (u)
  92.                     to = t[t[u].suf].go[i];
  93.                 if (t[u].go[i] != -1)
  94.                 {
  95.                     t[t[u].go[i]].suf = to;
  96.                     q.push(t[u].go[i]);
  97.                 }
  98.                 else
  99.                 {
  100.                     t[u].go[i] = to;
  101.                 }
  102.             }
  103.         }
  104.     }
  105.     void run(string s)
  106.     {
  107.         int u = 0;
  108.         for (int i = 0; i < (int)s.size(); ++i)
  109.         {
  110.             u = t[u].go[s[i] - 'a'];
  111.             ++t[u].cnt;
  112.         }
  113.     }
  114.     ll calc(int u)
  115.     {
  116.         if (dp[u] != -1)
  117.             return dp[u];
  118.         dp[u] = t[u].cnt;
  119.         for (int to : g[u])
  120.             dp[u] += calc(to);
  121.         return dp[u];
  122.     }
  123. };
  124.  
  125. int solve()
  126. {
  127.     int n;
  128.     scanf("%d", &n);
  129.     Trie T;
  130.     vi tpos(n);
  131.     for (int i = 0; i < n; ++i)
  132.     {
  133.         tpos[i] = T.adds(get_str());
  134.     }
  135.     T.buildAK();
  136.     T.run(get_str());
  137.     for (int i = 0; i < n; ++i)
  138.     {
  139.     if (TASK == "search5")
  140.         printf("%lld\n", T.calc(tpos[i]));
  141.     else
  142.         puts((T.calc(tpos[i])) ? "YES" : "NO");
  143.     }
  144.     return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement