fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. using pii = pair<int,int>;
  5.  
  6. struct Hash {
  7. static const int base1 = 311, base2 = 991;
  8. static const int mod1 = 1000000711, mod2 = 1234567891;
  9. vector<int> pw1, pw2, h1, h2;
  10. void assign(const string &s) {
  11. int n = s.size();
  12. pw1.assign(n+1,0);
  13. pw2.assign(n+1,0);
  14. h1.assign(n+1,0);
  15. h2.assign(n+1,0);
  16. pw1[0] = pw2[0] = 1;
  17. for(int i = 1; i <= n; i++){
  18. pw1[i] = (pw1[i-1] * 1LL * base1) % mod1;
  19. pw2[i] = (pw2[i-1] * 1LL * base2) % mod2;
  20. int v = s[i-1] - 'a' + 1;
  21. h1[i] = (h1[i-1] * 1LL * base1 + v) % mod1;
  22. h2[i] = (h2[i-1] * 1LL * base2 + v) % mod2;
  23. }
  24. }
  25. pii get(int L, int R){
  26. int x1 = (h1[R] - h1[L-1] * 1LL * pw1[R-L+1] % mod1 + mod1) % mod1;
  27. int x2 = (h2[R] - h2[L-1] * 1LL * pw2[R-L+1] % mod2 + mod2) % mod2;
  28. return {x1, x2};
  29. }
  30. };
  31.  
  32. bool equal_hash(const pii &A, const pii &B){
  33. return A.first == B.first && A.second == B.second;
  34. }
  35.  
  36. signed main(){
  37. ios::sync_with_stdio(false);
  38. cin.tie(nullptr);
  39. freopen("foundstring.inp", "r", stdin);
  40. freopen("foundstring.out", "w", stdout);
  41. int n;
  42. string s, y;
  43. cin >> y >> s;
  44.  
  45. Hash a, b;
  46. a.assign(y);
  47. b.assign(s);
  48.  
  49. int yy = y.size(), ss = s.size();
  50. pii tmp = a.get(1, yy);
  51. vector<int> res;
  52. for(int i = 1; i <= ss - yy + 1; i++){
  53. if(tmp == b.get(i, i + yy - 1)) res.push_back(i);
  54. }
  55. cout << res.size() << endl;
  56. for(int i: res) cout << i << " ";
  57. return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5320KB
stdin
viet
vietnamnamvietviet
stdout
3
1 11 15