Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- typedef long long ll;
- typedef long double ld;
- #define sqrt sqrtl
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- using namespace std;
- ll b = 27;
- __int128 m = 1e32 + 7;
- /*istream& operator >> (istream& in, vector <T>& a) {
- fro(T & i:a) in >> i;
- return in;
- }
- template <typename T>
- ostream& operator << (istream& out, vector <T>& a) {
- for (T& i : a) {
- out < i << " ";
- }
- return out << ;
- }*/
- void do_h(string& s, vector <ll>& h, vector <ll>& p) {
- ll n = s.size(), i, j;
- h[0] = 0;
- p[0] = 1;
- for (i = 0; i < n; i++) {
- h[i + 1] = (h[i] * b + (s[i] - 'a' + 1)) % m;
- p[i + 1] = (p[i] * b) % m;
- }
- }
- ll get_h(ll l, ll r, vector <ll>& h, vector <ll>& p) {
- return h[r + 1] - (h[l] * p[r - l + 1]) % m;
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- string a, b;
- cin >> a >> b;
- ll i, j, n = a.size(), n1 = b.size();
- vector <ll> ans;
- vector <ll> h(a.size() + 1);
- vector <ll> p(a.size() + 1);
- vector <ll> h1(b.size() + 1);
- vector <ll> p1(b.size() + 1);
- do_h(a, h, p);
- do_h(b, h1, p1);
- for (i = 0; i <= n - n1; i++) {
- if (get_h(i, i + n1 - 1, h, p) == get_h(0, n1 - 1, h1, p1)) {
- ans.push_back(i + 1);
- }
- }
- cout << ans.size() << "\n";
- for (auto now : ans) cout << now << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement