Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ⠸⣷⣦⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠀⠀⠀
- ⠀⠙⣿⡄⠈⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠔⠊⠉⣿⡿⠁⠀⠀⠀
- ⠀⠀⠈⠣⡀⠀⠀⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠁⠀⠀⣰⠟⠀⠀⠀⣀⣀
- ⠀⠀⠀⠀⠈⠢⣄⠀⡈⠒⠊⠉⠁⠀⠈⠉⠑⠚⠀⠀⣀⠔⢊⣠⠤⠒⠊⠉⡜
- ⠀⠀⠀⠀⠀⠀⠀⡽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠩⡔⠊⠁⠀⠀⠀⠀⠀ ⠀⠇
- ⠀⠀⠀⠀⠀⠀⠀⡇⢠⡤⢄⠀⠀⠀⠀⠀⡠⢤⣄⠀⡇⠀⠀⠀⠀⠀⠀⠀ ⢰⠀
- ⠀⠀⠀⠀⠀⠀⢀⠇⠹⠿⠟⠀⠀⠤⠀⠀⠻⠿⠟⠀⣇⠀⠀⡀⠠⠄⠒⠊⠁⠀
- ⠀⠀⠀⠀⠀⠀⢸⣿⣿⡆⠀⠰⠤⠖⠦⠴⠀⢀⣶⣿⣿⠀⠙⢄⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠀⠀⢻⣿⠃⠀⠀⠀⠀⠀⠀⠀⠈⠿⡿⠛⢄⠀⠀⠱⣄⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠀⠀⢸⠈⠓⠦⠀⣀⣀⣀⠀⡠⠴⠊⠹⡞⣁⠤⠒⠉⠀⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠀⣠⠃⠀⠀⠀⠀⡌⠉⠉⡤⠀⠀⠀⠀⢻⠿⠆⠀⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠰⠁⡀⠀⠀⠀⠀⢸⠀⢰⠃⠀⠀⠀⢠⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⢶⣗⠧⡀⢳⠀⠀⠀⠀⢸⣀⣸⠀⠀⠀⢀⡜⠀⣸⢤⣶⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⠈⠻⣿⣦⣈⣧⡀⠀⠀⢸⣿⣿⠀⠀⢀⣼⡀⣨⣿⡿⠁⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠈⠻⠿⠿⠓⠄⠤⠘⠉⠙⠤⢀⠾⠿⣿⠟⠋
- */
- #include <iostream>
- #include <string>
- #include <sstream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <memory.h>
- #include <stdio.h>
- #include <stack>
- #include <deque>
- #include <queue>
- #include <set>
- #include <iterator>
- #include <map>
- #include <iomanip>
- #include <unordered_set>
- #define int long long
- #define pb push_back
- #define intt __int128
- #define double long double
- #define endl "\n"
- #define fir first
- #define sec second
- #define un unsigned
- #define INF 1000000007
- #define EPS 0.00000000000000001
- #define pii pair<int, int>
- #define all(v) v.begin(), v.end()
- using namespace std;
- const int N = 1000009;
- struct Hash
- {
- int h1, h2;
- Hash(int x, int y) : h1(x), h2(y) {}
- Hash(int x) : h1(x), h2(x) {}
- Hash() : h1(0), h2(0) {}
- };
- const Hash P = { 31, 37 }, MOD = { (int)1e9 + 7, (int)1e9 + 9 };
- vector<Hash> pw(N);
- Hash operator + (Hash a, Hash b)
- {
- return { (a.h1 + b.h1) % MOD.h1, (a.h2 + b.h2) % MOD.h2 };
- }
- Hash operator - (Hash a, Hash b)
- {
- return { (a.h1 - b.h1 + MOD.h1) % MOD.h1, (a.h2 - b.h2 + MOD.h2) % MOD.h2 };
- }
- Hash operator * (Hash a, Hash b)
- {
- return { (a.h1 * b.h1) % MOD.h1, (a.h2 * b.h2) % MOD.h2 };
- }
- Hash operator % (Hash a, Hash b)
- {
- return { a.h1 % b.h1, a.h2 % b.h2 };
- }
- Hash operator * (Hash a, int b)
- {
- return { (a.h1 * b) % MOD.h1, (a.h2 * b) % MOD.h2 };
- }
- bool operator != (Hash a, Hash b)
- {
- return a.h1 != b.h1 || a.h2 != b.h2;
- }
- bool operator == (Hash a, Hash b)
- {
- return a.h1 == b.h1 && a.h2 == b.h2;
- }
- void build_powers()
- {
- pw[0] = 1;
- for (int i = 1; i < N; i++)
- {
- pw[i] = pw[i - 1] * P;
- }
- return;
- }
- vector<Hash> build_hash(string s)
- {
- vector<Hash> hs((int)s.size());
- hs[0] = 0;
- for (int i = 1; i < (int)s.size(); i++)
- {
- hs[i] = hs[i - 1] + pw[i] * s[i];
- }
- return hs;
- }
- Hash get_hash(vector<Hash>& hs, int l, int r)
- {
- return hs[r] - hs[l - 1];
- }
- signed main()
- {
- ios_base::sync_with_stdio();
- cin.tie(0);
- cout.tie(0);
- cout.precision(20);
- int n;
- cin >> n;
- string s, t;
- cin >> s >> t;
- s = "1" + s;
- t = "1" + t;
- build_powers();
- vector<Hash> hs = build_hash(s), ht = build_hash(t);
- int ans = 0;
- int r = t.size() - 1;
- int l = 1;
- int sz = 0;
- bool flag = 0;
- string check = "";
- for (int i = 1; i < s.size(); i++)
- {
- check += s[i];
- sz++;
- int l1 = max(1LL, r - sz + 1);
- int r1 = l + sz - 1;
- Hash q1 = get_hash(hs, l, r1) * pw[l1];
- Hash q2 = get_hash(ht, l1, r) * pw[l];
- if (q1 == q2)
- {
- check = "";
- l = i + 1;
- r = t.size() - i - 1;
- sz = 0;
- }
- }
- if (check == "")
- {
- cout << "YES";
- }
- else
- {
- cout << "NO";
- }
- return 0;
- }
- // скинула жопу
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement