Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define hii cout << "hii" << endl
- // #define int ll
- #define endl '\n'
- #define all(s) s.begin(), s.end()
- template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
- template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
- template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
- template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
- #ifndef ONLINE_JUDGE
- #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
- template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
- template <class Arg1, class... Args>
- void __f(const char* names, Arg1&& arg1, Args&&... args) {
- const char* sep = strchr(names + 1, ',');
- cerr.write(names, sep - names) << " : " << arg1 << " ";
- __f(sep + 1, args...);
- }
- #else
- #define trace(...) 0
- #pragma GCC optimize ("O3")
- #pragma GCC optimize ("unroll-loops")
- #pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #define _CRT_SECURE_NO_WARNINGS
- #endif // ifndef ONLINE_JUDGE
- const int N = 5e5 + 5;
- const int MAXN = 1e4 + 5;
- const int M = 3e5;
- const int mod = 1e9 + 7;
- const int MOD = 1e9 + 7;
- // const int INF = 1e15;
- const int LG = 21;
- int arr[N];
- int brr[N];
- int suff1[N];
- int suff2[N];
- struct Hashs
- {
- vector<int> hashs;
- vector<int> pows;
- int P;
- int MOD;
- Hashs() {}
- Hashs(string &s, int P, int MOD) : P(P), MOD(MOD)
- {
- int n = s.size();
- pows.resize(n+1, 0);
- hashs.resize(n+1, 0);
- pows[0] = 1;
- for(int i=n-1;i>=0;i--)
- {
- hashs[i]=(1LL * hashs[i+1] * P + s[i] - 'a' + 1) % MOD;
- pows[n-i]=(1LL * pows[n-i-1] * P) % MOD;
- }
- pows[n] = (1LL * pows[n-1] * P)%MOD;
- }
- int get_hash(int l, int r)
- {
- int ans=hashs[l] + MOD - (1LL*hashs[r+1]*pows[r-l+1])%MOD;
- ans%=MOD;
- return ans;
- }
- };
- void solve()
- {
- int n;
- while(cin >> n)
- {
- string input1;
- string input2;
- cin >> input1 >> input2;
- int n = input1.size();
- int m = input2.size();
- Hashs hh1(input1, 137, 1e9 + 123), hh2(input1, 239, 1e9 + 7);
- Hashs gg1(input2, 137, 1e9 + 123), gg2(input2, 239, 1e9 + 7);
- int x1 = hh1.get_hash(0, n - 1);
- int x2 = hh2.get_hash(0, n - 1);
- trace(x1, x2);
- for(int i = 0; i + n - 1 <= m - 1; i++)
- {
- if(gg1.get_hash(i, i + n - 1) == x1 and gg2.get_hash(i, i + n - 1) == x2)
- {
- cout << i << endl;
- }
- }
- cout << endl;
- }
- }
- int32_t main()
- {
- ios_base:: sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- // #ifndef ONLINE_JUDGE
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // #endif
- int t = 1;
- // cin >> t;
- while(t--)solve();
- return 0;
- }
Add Comment
Please, Sign In to add comment