fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11.  
  12. const int N = 5e5+5;
  13.  
  14. int k;
  15. string s;
  16.  
  17. int go[N][26], fail[N], cnt[N], nodes = 0;
  18. vector<int> order;
  19.  
  20. int insert(string s) {
  21.     int u = 0;
  22.     for (char ch : s) {
  23.         int c = ch - 'a';
  24.         if (!go[u][c]) go[u][c] = ++nodes;
  25.         u = go[u][c];
  26.     }
  27.     return u;
  28. }
  29.  
  30. void build() {
  31.     queue<int> q;
  32.     for (int c = 0; c < 26; c++)
  33.         if (go[0][c]) q.push(go[0][c]);
  34.     while (!q.empty()) {
  35.         int u = q.front(); q.pop();
  36.         order.push_back(u);
  37.         for (int c = 0; c < 26; c++) {
  38.             if (go[u][c]) {
  39.                 fail[go[u][c]] = go[fail[u]][c];
  40.                 q.push(go[u][c]);
  41.             } else go[u][c] = go[fail[u]][c];
  42.         }
  43.     } 
  44. }
  45.  
  46. void calc(string s) {
  47.     int u = 0;
  48.     for (char ch : s) {
  49.         int c = ch - 'a';
  50.         u = go[u][c];
  51.         cnt[u]++;
  52.     }
  53.     for (int i = (int)order.size() - 1; i >= 0; i--) {
  54.         int u = order[i];
  55.         cnt[fail[u]] += cnt[u];
  56.     }
  57. }
  58.  
  59. void solve() {
  60.     cin >> s >> k;
  61.     vector<int> p(k);
  62.     for (int i = 0; i < k; i++) {
  63.         string w; cin >> w;
  64.         p[i] = insert(w);
  65.     }
  66.     build();
  67.     calc(s);
  68.     for (int i = 0; i < k; i++) cout << cnt[p[i]] << '\n';
  69. }
  70.  
  71. int main() {
  72.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  73.  
  74.     int tests = 1; // cin >> tests;
  75.     while (tests--) solve();
  76.  
  77.     #ifdef LOCAL
  78.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  79.     #endif
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
aybabtu
3
bab
abc
a
stdout
copy 
1
0
2
https://ideone.com/p3KOTX
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!