Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, to[1501][128], link[1501], word[1501], sz = 0;
  6. bool leaf[1501];
  7. string t;
  8.  
  9. void init_trie()
  10. {
  11.     memset(to, 0, sizeof(to));
  12.     memset(leaf, false, sizeof(leaf));
  13.     memset(link, 0, sizeof(link));
  14.     memset(word, 0, sizeof(word));
  15. }
  16.  
  17. void add_str(string s, int id)
  18. {
  19.     int u = 0;
  20.     for (int i = 0; i < s.size(); i++)
  21.     {
  22.         int j = s[i];
  23.         if (to[u][s[i]] == 0)
  24.             to[u][j] = ++sz;
  25.         u = to[u][j];
  26.     }
  27.     leaf[u] = true;
  28.     word[u] = id;
  29. }
  30.  
  31. void push_link()
  32. {
  33.     queue<int> q;
  34.     q.push(0);
  35.     while (!q.empty())
  36.     {
  37.         int u = q.front();
  38.         q.pop();
  39.         int v = link[u];
  40.         leaf[u] |= leaf[v];
  41.         for (int i = 0; i < 128; i++)
  42.             if (to[u][i] != 0)
  43.             {
  44.                 link[to[u][i]] = ((u != 0) ? to[v][i] : 0);
  45.                 q.push(to[u][i]);
  46.             }
  47.         else
  48.         to[u][i] = to[v][i];
  49.     }
  50. }
  51.  
  52. int search_str(string s)
  53. {
  54.     int cnt = 0, u = 0;
  55.     for (int i = 0; i < s.size(); i++)
  56.     {
  57.         u = to[u][s[i]];
  58.         int v = u;
  59.         while (leaf[v])
  60.         {
  61.             if (word[v] != 0)
  62.                 cnt++;
  63.             v = link[v];
  64.         }
  65.     }
  66.     return cnt;
  67. }
  68.  
  69. int main()
  70. {
  71.     freopen("find_patterns.inp", "r", stdin);
  72.     freopen("find_patterns.out", "w", stdout);
  73.     init_trie();
  74.     getline(cin, t);
  75.     scanf("%d\n", &n);
  76.     for (int i = 1; i <= n; i++)
  77.     {
  78.         char s[15];
  79.         scanf("%s\n", &s);
  80.         add_str(s, i);
  81.     }
  82.     push_link();
  83.     printf("%d\n", search_str(t));
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement