Advertisement
ke_timofeeva7

чето из дп, которое решается без дп

Nov 6th, 2021
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.30 KB | None | 0 0
  1. /*
  2. ⠸⣷⣦⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠀⠀⠀
  3. ⠀⠙⣿⡄⠈⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠔⠊⠉⣿⡿⠁⠀⠀⠀
  4. ⠀⠀⠈⠣⡀⠀⠀⠑⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠁⠀⠀⣰⠟⠀⠀⠀⣀⣀
  5. ⠀⠀⠀⠀⠈⠢⣄⠀⡈⠒⠊⠉⠁⠀⠈⠉⠑⠚⠀⠀⣀⠔⢊⣠⠤⠒⠊⠉⡜
  6. ⠀⠀⠀⠀⠀⠀⠀⡽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠩⡔⠊⠁⠀⠀⠀⠀⠀ ⠀⠇
  7. ⠀⠀⠀⠀⠀⠀⠀⡇⢠⡤⢄⠀⠀⠀⠀⠀⡠⢤⣄⠀⡇⠀⠀⠀⠀⠀⠀⠀ ⢰⠀
  8. ⠀⠀⠀⠀⠀⠀⢀⠇⠹⠿⠟⠀⠀⠤⠀⠀⠻⠿⠟⠀⣇⠀⠀⡀⠠⠄⠒⠊⠁⠀
  9. ⠀⠀⠀⠀⠀⠀⢸⣿⣿⡆⠀⠰⠤⠖⠦⠴⠀⢀⣶⣿⣿⠀⠙⢄⠀⠀⠀⠀⠀⠀
  10. ⠀⠀⠀⠀⠀⠀⠀⢻⣿⠃⠀⠀⠀⠀⠀⠀⠀⠈⠿⡿⠛⢄⠀⠀⠱⣄⠀⠀⠀⠀
  11. ⠀⠀⠀⠀⠀⠀⠀⢸⠈⠓⠦⠀⣀⣀⣀⠀⡠⠴⠊⠹⡞⣁⠤⠒⠉⠀⠀⠀⠀⠀
  12. ⠀⠀⠀⠀⠀⠀⣠⠃⠀⠀⠀⠀⡌⠉⠉⡤⠀⠀⠀⠀⢻⠿⠆⠀⠀⠀⠀⠀⠀⠀
  13. ⠀⠀⠀⠀⠀⠰⠁⡀⠀⠀⠀⠀⢸⠀⢰⠃⠀⠀⠀⢠⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀
  14. ⠀⠀⠀⢶⣗⠧⡀⢳⠀⠀⠀⠀⢸⣀⣸⠀⠀⠀⢀⡜⠀⣸⢤⣶⠀⠀⠀⠀⠀⠀
  15. ⠀⠀⠀⠈⠻⣿⣦⣈⣧⡀⠀⠀⢸⣿⣿⠀⠀⢀⣼⡀⣨⣿⡿⠁⠀⠀⠀⠀⠀⠀
  16. ⠀⠀⠀⠀⠀⠈⠻⠿⠿⠓⠄⠤⠘⠉⠙⠤⢀⠾⠿⣿⠟⠋
  17. */
  18.  
  19. #include <iostream>
  20. #include <string>
  21. #include <sstream>
  22. #include <vector>
  23. #include <cmath>
  24. #include <algorithm>
  25. #include <memory.h>
  26. #include <stdio.h>
  27. #include <stack>
  28. #include <deque>
  29. #include <queue>
  30. #include <set>
  31. #include <iterator>
  32. #include <map>
  33. #include <iomanip>
  34. #include <unordered_set>
  35. #define int long long
  36. #define pb push_back
  37. #define intt __int128
  38. #define double long double
  39. #define endl "\n"
  40. #define fir first
  41. #define sec second
  42. #define un unsigned
  43. #define INF 1000000007
  44. #define EPS 0.00000000000000001
  45. #define pii pair<int, int>
  46. #define all(v) v.begin(), v.end()
  47. using namespace std;
  48.  
  49. const int N = 1000009;
  50.  
  51. struct Hash
  52. {
  53.     int h1, h2;
  54.  
  55.     Hash(int x, int y) : h1(x), h2(y) {}
  56.     Hash(int x) : h1(x), h2(x) {}
  57.     Hash() : h1(0), h2(0) {}
  58. };
  59.  
  60. const Hash P = { 31, 37 }, MOD = { (int)1e9 + 7, (int)1e9 + 9 };
  61.  
  62. vector<Hash> pw(N);
  63.  
  64. Hash operator + (Hash a, Hash b)
  65. {
  66.     return { (a.h1 + b.h1) % MOD.h1, (a.h2 + b.h2) % MOD.h2 };
  67. }
  68.  
  69. Hash operator - (Hash a, Hash b)
  70. {
  71.     return { (a.h1 - b.h1 + MOD.h1) % MOD.h1, (a.h2 - b.h2 + MOD.h2) % MOD.h2 };
  72. }
  73.  
  74. Hash operator * (Hash a, Hash b)
  75. {
  76.     return { (a.h1 * b.h1) % MOD.h1, (a.h2 * b.h2) % MOD.h2 };
  77. }
  78.  
  79. Hash operator % (Hash a, Hash b)
  80. {
  81.     return { a.h1 % b.h1, a.h2 % b.h2 };
  82. }
  83.  
  84. Hash operator * (Hash a, int b)
  85. {
  86.     return { (a.h1 * b) % MOD.h1, (a.h2 * b) % MOD.h2 };
  87. }
  88.  
  89. bool operator != (Hash a, Hash b)
  90. {
  91.     return a.h1 != b.h1 || a.h2 != b.h2;
  92. }
  93.  
  94. bool operator == (Hash a, Hash b)
  95. {
  96.     return a.h1 == b.h1 && a.h2 == b.h2;
  97. }
  98.  
  99. void build_powers()
  100. {
  101.     pw[0] = 1;
  102.  
  103.     for (int i = 1; i < N; i++)
  104.     {
  105.         pw[i] = pw[i - 1] * P;
  106.     }
  107.  
  108.     return;
  109. }
  110.  
  111. vector<Hash> build_hash(string s)
  112. {
  113.     vector<Hash> hs((int)s.size());
  114.     hs[0] = 0;
  115.  
  116.     for (int i = 1; i < (int)s.size(); i++)
  117.     {
  118.         hs[i] = hs[i - 1] + pw[i] * s[i];
  119.     }
  120.  
  121.     return hs;
  122. }
  123.  
  124. Hash get_hash(vector<Hash>& hs, int l, int r)
  125. {
  126.     return hs[r] - hs[l - 1];
  127. }
  128.  
  129. signed main()
  130. {
  131.     ios_base::sync_with_stdio();
  132.     cin.tie(0);
  133.     cout.tie(0);
  134.     cout.precision(20);
  135.  
  136.     int n;
  137.     cin >> n;
  138.  
  139.     string s, t;
  140.     cin >> s >> t;
  141.  
  142.     s = "1" + s;
  143.     t = "1" + t;
  144.  
  145.     build_powers();
  146.  
  147.     vector<Hash> hs = build_hash(s), ht = build_hash(t);
  148.  
  149.     int ans = 0;
  150.     int r = t.size() - 1;
  151.     int l = 1;
  152.     int sz = 0;
  153.  
  154.     bool flag = 0;
  155.  
  156.     string check = "";
  157.  
  158.     for (int i = 1; i < s.size(); i++)
  159.     {
  160.         check += s[i];
  161.         sz++;
  162.  
  163.         int l1 = max(1LL, r - sz + 1);
  164.         int r1 = l + sz - 1;
  165.  
  166.         Hash q1 = get_hash(hs, l, r1) * pw[l1];
  167.         Hash q2 = get_hash(ht, l1, r) * pw[l];
  168.  
  169.         if (q1 == q2)
  170.         {
  171.             check = "";
  172.             l = i + 1;
  173.             r = t.size() - i - 1;
  174.             sz = 0;
  175.         }
  176.     }
  177.  
  178.     if (check == "")
  179.     {
  180.         cout << "YES";
  181.     }
  182.     else
  183.     {
  184.         cout << "NO";
  185.     }
  186.  
  187.     return 0;
  188. }
  189. // скинула жопу
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement