fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define F0R(i, a) for(int i = 0; i < (a); i++)
  4. #define FOR(i, a, b) for(int i = (a); i < (b); i++)
  5. #define R0F(i, a) for(int i = (a) - 1; i >= 0; i--)
  6. #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); i--)
  7.  
  8. #define ran() (rand() & 0x7FFF)
  9. #define rand31() ((ran() << 16) | (ran() << 1) | (ran() & 1))
  10. #define rand32() ((ran() << 17) | (ran() << 2) | (ran() & 3))
  11. #define rand63() (((ll)ran() << 48) | ((ll)ran() << 33) | ((ll)ran() << 18) | ((ll)ran() << 3) | ((ll)ran() & 7))
  12. #define rand64() (((ll)ran() << 49) | ((ll)ran() << 34) | ((ll)ran() << 19) | ((ll)ran() << 4) | ((ll)ran() & 15))
  13.  
  14. #define F first
  15. #define S second
  16. #define PB push_back
  17. #define MP make_pair
  18. #define MT make_tuple
  19. #define UB upper_bound
  20. #define LB lower_bound
  21. #define X real()
  22. #define Y imag()
  23.  
  24. #define PI acos(-1)
  25.  
  26. #define sz(x) ((int)(x).size())
  27. #define all(x) (x).begin(), (x).end()
  28. #define SQ(x) ((x) * (x))
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef long double ld;
  34. typedef unsigned long long ull;
  35. typedef pair<int, int> pii;
  36. typedef vector<int> vi;
  37. typedef vector<pii> vpii;
  38. typedef vector<ll> vll;
  39. typedef vector<ull> vul;
  40. typedef complex<ld> point;
  41. typedef complex<ld> cld;
  42. typedef vector<cld> vcld;
  43.  
  44. vi z(string s) {
  45.     int N = s.length(); s += '#';
  46.     vi ans(N); ans[0] = N;
  47.     while (s[1+ans[1]] == s[ans[1]]) ans[1] ++;
  48.  
  49.     int L = 1, R = ans[1];
  50.     FOR(i,2,N) {
  51.         if (i <= R) ans[i] = min(R-i+1,ans[i-L]);
  52.         while (s[i+ans[i]] == s[ans[i]]) ans[i] ++;
  53.         if (i+ans[i]-1 > R) L = i, R = i+ans[i]-1;
  54.     }
  55.     return ans;
  56. }
  57.  
  58. int main() {
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     while(!cin.eof()) {
  62.         string p, s;
  63.         getline(cin, p);
  64.         getline(cin, s);
  65.         vi v = z(p + "&" + s);
  66.         vi r;
  67.         F0R(i, sz(v)) if(v[i] == sz(p)) r.PB(i - sz(p) - 1);
  68.         F0R(i, sz(r)) {
  69.             if(i > 0) cout << " ";
  70.             cout << r[i];
  71.         }
  72.         cout << "\n";
  73.     }   
  74. }
Success #stdin #stdout 0s 4592KB
comments (?)
stdin
copy 
m
aaaaamaaaaaa
stdout
copy 
5
https://ideone.com/H5ooLY
language:
C++14 (gcc 8.3)
created:
5 years 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!