fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2026-03-04 23:24:15
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2026-04-04 15:20:41
  6. */
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #define int long long
  10. #define MOD 1000000007
  11. const int N = (int)1e6+10, base = 311;
  12. string A,B;
  13. int hashA[N],hashB,pw[N];
  14.  
  15. int hashing(int hashVal, char h) {
  16.     return (hashVal*base%MOD+h)%MOD;
  17. }
  18.  
  19. int getHash(int l, int r) {
  20.     return (hashA[r]-hashA[l-1]*pw[r-l+1]%MOD+MOD)%MOD;
  21. }
  22.  
  23. signed main()
  24. {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(NULL); cout.tie(NULL);
  27.     cin >> A >> B;
  28.     pw[0] = 1;
  29.     int n = A.size(), m = B.size();
  30.     A = '#'+A; B = '#'+B;
  31.     for (int i = 1; i <= n; i++)
  32.     {
  33.         pw[i] = pw[i-1]*base%MOD;
  34.         hashA[i] = hashing(hashA[i-1],A[i]);
  35.     }
  36.     for (int i = 1; i <= m; i++) hashB = hashing(hashB,B[i]);
  37.     for (int i = 1; i <= n-m+1; i++)
  38.         if (getHash(i,i+m-1) == hashB) cout << i << " ";
  39.     return 0;
  40. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/aBirAq
language:
C++14 (gcc 8.3)
created:
6 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!