fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int base = 311;
  6. const long long mod = 1e9 + 7;
  7. //
  8. int q;
  9. long long hashS[mx], hashT[mx], power[mx] = {1};
  10. unordered_map<long long, int> ans[mx];
  11. string S, T[mx];
  12. //
  13. long long hash_value (string &s)
  14. {
  15.     long long res = 0;
  16.     //
  17.     for (char c : s)
  18.         res = (res * base + c) % mod;
  19.     return res;
  20. }
  21. long long get (int l, int r)
  22. {
  23.     return (hashS[r] - hashS[l] * power[r - l] + mod * mod) % mod;
  24. }
  25. void prepare (void)
  26. {
  27.     for (int i = 1; i < mx; ++i)
  28.         power[i] = power[i - 1] * base % mod;
  29.     for (size_t i = 1; i <= S.size(); ++i)
  30.         hashS[i] = (hashS[i - 1] * base + S[i - 1]) % mod;
  31.     for (int i = 0; i < q; ++i)
  32.         hashT[i] = hash_value(T[i]),
  33.         ans[T[i].size()][hashT[i]] = 0;
  34. }
  35. void solve (int len)
  36. {
  37.     long long val;
  38.     //
  39.     for (int i = 0; i <= S.size() - len; ++i)
  40.     {
  41.         val = get(i, i + len);
  42.         if (ans[len].find(val) != ans[len].end())
  43.             ++ans[len][val];
  44.     }
  45. }
  46. //
  47. void process (void)
  48. {
  49.     cin >> S >> q;
  50.     for (int i = 0; i < q; ++i)
  51.         cin >> T[i];
  52.  
  53.     prepare();
  54.     for (int i = 1; i < mx; ++i)
  55.         if (!ans[i].empty())
  56.             solve(i);
  57.  
  58.     for (int i = 0; i < q; ++i)
  59.         cout << ans[T[i].size()][hashT[i]] << '\n';
  60. }
  61. //
  62. signed main (void)
  63. {
  64.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  65.     process();
  66. }
Success #stdin #stdout 0.01s 13648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8TnSKy
https://m...content-available-to-author-only...j.com/problem/258
language:
C++14 (gcc 8.3)
created:
10 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!