fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 1e5+5;
  5. const int mod = 1e9 + 7;
  6. const int oo = 1e18+5;
  7. typedef pair<int, int> ii;
  8. typedef pair<int, pair<int, int>> iii;
  9. #define fi first
  10. #define se second
  11. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  12. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  13. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  14. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  15. #define file "main"
  16. #define bit(x, i) ((x >> i) & 1)
  17. #define bat(x, i) (x | (1 << i))
  18.  
  19. int n, m;
  20. int a[maxn], b[maxn], res;
  21. string ss[maxn];
  22.  
  23. const int maxT = 2e6+5;
  24.  
  25. string s;
  26.  
  27. struct Node
  28. {
  29.     int next[26] = {0};
  30.     int ex = 0;
  31.     int d = 0;
  32.     int c = 0;
  33. };
  34.  
  35. Node T[maxT];
  36. int nT = 0;
  37.  
  38. void add(string s)
  39. {
  40.     int u = 0;
  41.     for(int i = 0; i < s.size(); i++)
  42.     {
  43.         if(!T[u].next[s[i] - 'a']) T[u].next[s[i] - 'a'] = ++nT;
  44.         int pos = u;
  45.         u = T[u].next[s[i] - 'a'];
  46.         T[u].c++;
  47.     }
  48.     T[u].ex++;
  49. }
  50.  
  51. bool Find(string s)
  52. {
  53.     int u = 0;
  54.     for(int i = 0; i < s.size(); i++)
  55.     {
  56.         if(T[u].next[s[i] - 'a'] == 0) return false;
  57.         u = T[u].next[s[i] - 'a'];
  58.     }
  59.     return T[u].ex != 0;
  60. }
  61.  
  62. int cnt(string s)
  63. {
  64.     int res = 0;
  65.     int u = 0;
  66.     for(int i = 0; i < s.size(); i++)
  67.     {
  68.         if(T[u].next[s[i] - 'a'] == 0) return 0;
  69.         u = T[u].next[s[i] - 'a'];
  70.         res += T[u].c;
  71.     }
  72.     return res;
  73. }
  74.  
  75. map<string, int> mp;
  76. pair<string,int> tv[maxn];
  77. int ans[maxn];
  78.  
  79. bool cmp(pair<string,int> a, pair<string,int> b)
  80. {
  81.     return mp[a.fi] < mp[b.fi];
  82. }
  83.  
  84. int32_t main()
  85. {
  86.     fastIO;
  87.     File(file ".inp", file ".out");
  88.  
  89.     cin >> n;
  90.     for(int i = 1; i <= n; i++)
  91.     {
  92.         cin >> ss[i];
  93.         if(mp[ss[i]] == 0) mp[ss[i]] = i;
  94.     }
  95.     int q;
  96.     cin >> q;
  97.     for(int i = 1; i <= q; i++)
  98.     {
  99.         cin >> tv[i].fi;
  100.         if(mp[tv[i].fi] == 0) mp[tv[i].fi] = n+1;
  101.         tv[i].se = i;
  102.     }
  103.     sort(tv+1, tv+q+1, cmp);
  104.     int cntt = 1;
  105.     For(i, 1, n)
  106.     {
  107.         add(ss[i]);
  108.         while(cntt <= q && Find(tv[cntt].fi) && mp[tv[cntt].fi] <= i)
  109.         {
  110.             ans[tv[cntt].se] = cnt(tv[cntt].fi) + mp[tv[cntt].fi];
  111.             cntt++;
  112.         }
  113.     }
  114.     For(i, cntt, q)
  115.     {
  116.         if(ans[tv[i].se] == 0) ans[tv[i].se] = cnt(tv[i].fi) + n;
  117.     }
  118.     For(i, 1, q)
  119.     {
  120.         cout << ans[i] << '\n';
  121.     }
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 14796KB
comments (?)
stdin 
5
abcd
badf
aad
bcf
abdxe
4
abc
aad
bc
bad
stdout 
11
7
8
9
https://ideone.com/z1vp8b
language:
C++14 (gcc 8.3)
created:
1 day 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!