Advertisement
ivnikkk

Untitled

Oct 14th, 2021
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16. #define sqrt sqrtl
  17. #define endl "\n"
  18. #define all(a) a.begin(), a.end()
  19. using namespace std;
  20. ll b = 27;
  21. __int128 m = 1e32 + 7;
  22. /*istream& operator >> (istream& in, vector <T>& a) {
  23.     fro(T & i:a) in >> i;
  24.     return in;
  25. }
  26. template <typename T>
  27. ostream& operator << (istream& out, vector <T>& a) {
  28.     for (T& i : a) {
  29.         out < i << " ";
  30.     }
  31.     return out << ;
  32. }*/
  33. void do_h(string& s, vector <ll>& h, vector <ll>& p) {
  34.     ll n = s.size(), i, j;
  35.     h[0] = 0;
  36.     p[0] = 1;
  37.     for (i = 0; i < n; i++) {
  38.         h[i + 1] = (h[i] * b + (s[i] - 'a' + 1)) % m;
  39.         p[i + 1] = (p[i] * b) % m;
  40.     }
  41. }
  42. ll get_h(ll l, ll r, vector <ll>& h, vector <ll>& p) {
  43.     return h[r + 1] - (h[l] * p[r - l + 1]) % m;
  44. }
  45.  
  46. signed main() {
  47.     ios_base::sync_with_stdio(0);
  48.     cin.tie(NULL);
  49.     cout.tie(NULL);
  50.     string a, b;
  51.     cin >> a >> b;
  52.     ll i, j, n = a.size(), n1 = b.size();
  53.     vector <ll> ans;
  54.     vector <ll> h(a.size() + 1);
  55.     vector <ll> p(a.size() + 1);
  56.     vector <ll> h1(b.size() + 1);
  57.     vector <ll> p1(b.size() + 1);
  58.     do_h(a, h, p);
  59.     do_h(b, h1, p1);
  60.     for (i = 0; i <= n - n1; i++) {
  61.         if (get_h(i, i + n1 - 1, h, p) == get_h(0, n1 - 1, h1, p1)) {
  62.             ans.push_back(i + 1);
  63.         }
  64.     }
  65.     cout << ans.size() << "\n";
  66.     for (auto now : ans) cout << now << " ";
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement