Advertisement
double_trouble

Untitled

Oct 2nd, 2015
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <stdio.h>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <string>
  9.  
  10. #define F first
  11. #define S second
  12.  
  13. using namespace std;
  14.  
  15.  
  16. vector <string> ans;
  17. struct node
  18. {
  19.     node *p;
  20.     node *nxt[94];
  21.     int ind;
  22.     node  *lnk;
  23.     char c;
  24.     bool listt;
  25.     node()
  26.     {
  27.         lnk = p = NULL;
  28.         listt = 0;
  29.         for (int i = 0; i < 94; i++)
  30.             nxt[i] = NULL;
  31.         ind = -1;
  32.         c = 0;
  33.     }
  34.     node(node *_p, char _c, int _ind)
  35.     {
  36.         p = _p;
  37.         c = _c;
  38.         ind = _ind;
  39.         lnk = NULL;
  40.         listt = 0;
  41.         for (int i = 0; i < 94; i++)
  42.             nxt[i] = NULL;
  43.     }
  44. };
  45.  
  46. node *root;
  47.  
  48. void add_word(const string &s, int new_ind)
  49. {
  50.     node *inode = root;
  51.     for (int i = 0; i < s.size(); i++)
  52.     {
  53.         if (inode->nxt[s[i] - ' '] == NULL)
  54.             inode->nxt[s[i] - ' '] = new node(inode, s[i] - ' ', -1);
  55.         inode = inode->nxt[s[i] - ' '];
  56.     }
  57.     inode->ind = new_ind;
  58.     inode->listt = 1;
  59. }
  60.  
  61. void build()
  62. {
  63.     node *inode, *w;
  64.     vector <node*> q;
  65.     q.push_back(root);
  66.     for (int i = 0; i < q.size(); i++)
  67.     {
  68.         inode = q[i];
  69.         for (int j = 0; j < 94; j++)
  70.             if (inode->nxt[j] != NULL)
  71.                 q.push_back(inode->nxt[j]);
  72.         if (inode == root)
  73.             continue;
  74.         if (inode->p == root)
  75.         {
  76.             inode->lnk = root;
  77.             continue;
  78.         }
  79.         w = inode->p;
  80.         w = w->lnk;
  81.         while (w != NULL && w->nxt[inode->c] == NULL)
  82.             w = w->lnk;
  83.         //tree[w].next[tree[v].c]
  84.         inode->lnk = w ->nxt[inode->c] == NULL ? root : w->nxt[inode->c];
  85.         if (inode->ind == -1)
  86.             inode->ind = inode->lnk->ind;
  87.         if (inode->listt == 0)
  88.             inode->listt = inode->lnk->listt;
  89.     }
  90. }
  91.  
  92. node *go(node *inode, char c)
  93. {
  94.     while (inode != NULL && inode->nxt[c] == NULL)
  95.         inode = inode->lnk;
  96.     return inode == NULL ? root : inode->nxt[c];
  97. }
  98.  
  99. void bfs()
  100. {
  101.     node *inode;
  102.     vector <node*> q;
  103.     q.push_back(root);
  104.     for (int i = 0; i < q.size(); i++)
  105.     {
  106.         inode = q[i];
  107.         if (inode->lnk->listt)
  108.             inode->listt = 1;
  109.         for (int j = 0; j < 94; j++)
  110.             if (inode->nxt[j] != NULL)
  111.                 q.push_back(inode->nxt[j]);
  112.     }
  113. }
  114.  
  115. bool find_word(string &s)
  116. {
  117.     node *inode = root;
  118.     for (int i = 0; i < s.size(); i++)
  119.     {
  120.         inode = go(inode, s[i] - ' ');
  121.         if (inode->listt)
  122.         {
  123.             return true;
  124.         }
  125.     }
  126.     return false;
  127. }
  128.  
  129. int main()
  130. {
  131.     ios_base::sync_with_stdio(0);
  132.     //cin.tie(0);
  133.     //cout.tie(0);
  134.     //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  135.     //freopen("console.in", "r", stdin);freopen("console.out", "w", stdout);
  136.     string s;
  137.     int k;
  138.     cin >> k;
  139.     root = new node(NULL, NULL, -1);
  140.     for (int i = 0; i < k; i++)
  141.     {
  142.         cin >> s;
  143.         add_word(s, i);
  144.     }
  145.     build();
  146.     bfs();
  147.     while (getline(cin, s))
  148.     {
  149.         if (find_word(s))
  150.             cout << s << '\n';
  151.     }
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement