fork download
copy 
  1. #ifdef ONPC
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. #include <bits/stdc++.h>
  5. #define pii pair<int, int>
  6. typedef long long ll;
  7. #define int long long
  8. using namespace std;
  9.  
  10. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  11. int modmul(int a, int b, int M)
  12. {
  13.  
  14.     return ((a % M) * (b % M)) % M;
  15. }
  16.  
  17. ll modexp(ll a, ll e, ll mod)
  18. {
  19.     ll res = 1 % mod;
  20.     a %= mod;
  21.     while (e > 0)
  22.     {
  23.         if (e & 1)
  24.             res = (res * a) % mod;
  25.         a = (a * a) % mod;
  26.         e >>= 1;
  27.     }
  28.     return res;
  29. }
  30.  
  31. const long long mod = 1e9 + 7;
  32. const long long P = 51;
  33. void solve()
  34. {
  35.     string in;
  36.     cin >> in;
  37.     string t;
  38.     cin >> t;
  39.     if (t.length() > in.length())
  40.     {
  41.         return;
  42.     }
  43.     vector<int> primesPow(in.length() + 5);
  44.     long long p = 51;
  45.     primesPow[0] = 1;
  46.     for (int i = 1; i < primesPow.size(); ++i)
  47.     {
  48.         primesPow[i] = modmul(p, primesPow[i - 1], mod);
  49.     }
  50.     ll invP = modexp(P, mod - 2, mod); // inverse of P mod MOD
  51.     vector<int> inv_pow(in.length() + 5);
  52.     inv_pow[0] = 1;
  53.     for (int i = 1; i <= in.length(); ++i)
  54.         inv_pow[i] = modmul(inv_pow[i - 1], invP, mod);
  55.     // polynomial hash of the string
  56.     vector<long long>
  57.         hashes(in.length() + 1);
  58.     hashes[0] = 0;
  59.     for (int i = 0; i < hashes.size() - 1; ++i)
  60.     {
  61.         hashes[i + 1] = (hashes[i] + ((in[i] - 'a' + 1) * primesPow[i])) % mod;
  62.     }
  63.     long long hashT = 0;
  64.     for (int i = 0; i < t.length(); ++i)
  65.     {
  66.         hashT = (hashT + ((t[i] - 'a' + 1) * primesPow[i])) % mod;
  67.     }
  68.     set<int> ans;
  69.     int sizeT = t.length();
  70.     for (int i = 0; i <= in.length() - t.length(); ++i)
  71.     {
  72.         long long newHash = (hashes[i + sizeT] + mod - hashes[i]) % mod;
  73.         newHash = modmul(newHash, inv_pow[i], mod);
  74.         if (newHash == hashT)
  75.         {
  76.             ans.insert(i);
  77.         }
  78.     }
  79.     for (auto i : ans)
  80.     {
  81.         cout << i << ' ';
  82.     }
  83.     cout << endl;
  84. }
  85.  
  86. signed main()
  87. {
  88.     ios::sync_with_stdio(0);
  89.     cin.tie(0);
  90.     int t = 1;
  91. #ifdef ONPC
  92.     freopen("input.txt", "r", stdin);
  93. #endif
  94.     // cin >> t;
  95.     for (int i = 0; i < t; ++i)
  96.     {
  97.         solve();
  98.     }
  99. #ifdef ONPC
  100.     cerr << endl
  101.          << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  102. #endif
  103.     return 0;
  104. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
ababbababa
aba
stdout
copy 
0 5 7
https://ideone.com/7TM1Lm
language:
C++ (gcc 8.3)
created:
23 days 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!