fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1LL << (n))
  6. #define TASK ""
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8. #define lc(n) (n << 1)
  9. #define rc(n) ((n << 1) | 1)
  10.  
  11. #define fi first
  12. #define se second
  13. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  14. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  15.  
  16. #define mii map<int,int>
  17. #define umi unordered_map<int, int>
  18. #define pii pair<int,int>
  19. #define vi vector<int>
  20.  
  21. using namespace std;
  22.  
  23. const int oo = 1e18;
  24. const int mod = 1e9 + 7;
  25. const int nmax = 1e6 + 8;
  26. const int base = 31;
  27.  
  28. //string a, b;
  29. int n, m, p[nmax];
  30.  
  31. void tao(){
  32.     p[0] = 1;
  33.     for(int i = 1; i <= 1e6; ++i){
  34.         p[i] = (p[i - 1] * base) % mod;
  35.     }
  36. }
  37.  
  38. struct{
  39.     int h[nmax];
  40.     string s;
  41.     int get(int l, int r){
  42.         return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod;
  43.  
  44.     }
  45.     void pre(){
  46.         for(int i = 1; i < s.size(); ++i){
  47.             h[i] = (h[i - 1] * base + s[i] - 'a' + 1) % mod;
  48.         }
  49.     }
  50. } a, b;
  51.  
  52. main(){
  53.     fast;
  54.     openfile();
  55.     tao();
  56.     cin >> a.s >> b.s;
  57.     n = a.s.size(), m = b.s.size();
  58.     a.s = ' ' + a.s, b.s = ' ' + b.s;
  59.     a.pre(), b.pre();
  60.     int cnt = 0;
  61.     for(int i = 1; i <= n - m + 1; ++i){
  62.         if(a.get(i, i + m - 1) == b.get(1, m)){
  63.             cout << i << ' ';
  64.         }
  65.     }
  66. //    cout << cnt;
  67. }
  68.  
Success #stdin #stdout 0.01s 13528KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/PLUaNP
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!