fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 5e5 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37. const int base = 31;
  38. const long long nmod = 1ll * mod * mod;
  39.  
  40. string s, t;
  41. int ns, nt;
  42. long long Hash[N], Pow[N], HashT;
  43.  
  44. int Get(int l, int r) {
  45.  
  46.     /// Hash[r] - Hash[l - 1] * Base ^ (r - l + 1)
  47.  
  48.     /// abcd
  49.  
  50.     /// a ab abc abcd
  51.     /// 1 2   3   4
  52.  
  53.     /// [l = 2, r = 4]  =  abcd - a * base ^ 3 = s[4] - s[1] * base ^ (4 - 2 + 1)
  54.  
  55.  
  56.  
  57.     ///  942 - 9 * (10 ^ 2) = 942 - 900
  58.  
  59.     /// Pow[i] = Base ^ i
  60.  
  61.         return (Hash[r] - Hash[l - 1] * Pow[r - l + 1] + nmod) % mod;
  62.     }
  63.  
  64. inline void Read_Input() {
  65.     cin >> s >> t;
  66.     ns = s.size();
  67.     nt = t.size();
  68.  
  69.     s = ' ' + s;
  70.     t = ' ' + t;
  71.  
  72.  
  73.     /// Pow[i] = Base ^ i
  74.     Pow[0] = 1;
  75.     for (int i = 1; i <= ns; i++)
  76.         Pow[i] = Pow[i - 1] * base % mod;
  77.  
  78.  
  79.     /// Hash[i] = Bieu dien cua doan s[1, i]
  80.  
  81.     for (int i = 1; i <= ns; i++)
  82.         Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % mod;
  83.  
  84.     for (int i = 1; i <= nt; i++)
  85.         HashT = (HashT * base + t[i] - 'a' + 1) % mod;
  86. }
  87.  
  88. inline void Solve() {
  89.     for (int i = 1; i <= ns - nt + 1; i++) {
  90.  
  91.  
  92.         if (Get(i, i + nt - 1) == HashT) cout << i << " ";
  93.  
  94.     }
  95. }
  96.  
  97. Ti20_ntson {
  98. //    freopen(TASK".INP","r",stdin);
  99. //    freopen(TASK".OUT","w",stdout);
  100.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  101.     int T = 1;
  102. //    cin >> T;
  103.     while (T -- ) {
  104.         Read_Input();
  105.         Solve();
  106.     }
  107. }
  108.  
  109.  
  110.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/hsCnqN
language:
C++14 (gcc 8.3)
created:
1 day 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!