GerONSo

Untitled

Feb 9th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. /*
  2. ┓┏┓┏┓┃
  3. ┛┗┛┗┛┃
  4. ┓┏┓┏┓┃
  5. ┛┗┛┗┛┃
  6. ┓┏┓┏┓┃\○/
  7. ┛┗┛┗┛┃ / /
  8. ┓┏┓┏┓┃ノ
  9. ┛┗┛┗┛┃
  10. ┓┏┓┏┓┃
  11. ┛┗┛┗┛┃
  12. ┓┏┓┏┓┃
  13. ┛┗┛┗┛┃
  14. ┓┏┓┏┓┃
  15. ┛┗┛┗┛┃
  16. ┓┏┓┏┓┃┓
  17. ┛┗┛┗┛┃┃
  18. MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
  19. */
  20.  
  21. #define pragma
  22.  
  23. #ifdef pragma
  24. #pragma GCC optimize("Ofast")
  25. #pragma GCC optimize("no-stack-protector")
  26. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  27. #pragma GCC optimize("unroll-loops")
  28. #pragma GCC diagnostic ignored "-Wunused-result"
  29. #endif // pragma
  30.  
  31. #include<bits/stdc++.h>
  32. #include <ext/pb_ds/assoc_container.hpp>
  33. #include <ext/pb_ds/tree_policy.hpp>
  34.  
  35. #define ll long long
  36. #define all(x) begin(x), end(x)
  37. #define pb push_back
  38. #define x first
  39. #define y second
  40. #define int long long
  41. #define zero(two) memset(two, 0, sizeof(two))
  42.  
  43. using namespace std;
  44. using namespace __gnu_pbds;
  45.  
  46.  
  47. typedef vector<int> vi;
  48. typedef vector<bool> vb;
  49. typedef pair<int, int> pii;
  50. typedef long double ld;
  51. typedef vector<vi> matrix;
  52. template<typename T>
  53. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  54.  
  55. const ld PI = atan2(0, -1);
  56.  
  57. void seriy() {
  58. ios::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. cout << fixed << setprecision(10);
  62. #if _offline
  63. freopen("input.txt", "r", stdin);
  64. freopen("output.txt", "w", stdout);
  65. #endif
  66. }
  67.  
  68. const int BASE = 47;
  69. const int MOD = 998244353;
  70. const int MAXN = 2e5 + 10;
  71.  
  72. vi pows(MAXN);
  73. vi sh, th;
  74. string s, t;
  75.  
  76. vi get_hash(string &s) {
  77. int n = s.size() + 1;
  78. vi h(n);
  79. for(int i = 1; i < n; i++) {
  80. h[i] = (h[i - 1] + s[i - 1] * pows[i]) % MOD;
  81. }
  82. return h;
  83. }
  84.  
  85. int subhash(vi &h, int l, int r) {
  86. return ((h[r] - h[l - 1] + MOD) * pows[h.size() - l]) % MOD;
  87. }
  88.  
  89. bool equals(int tl, int tr, int l, int r) {
  90. if(subhash(sh, tl + 1, tr + 1) == subhash(th, l + 1, r + 1)) {
  91. return 1;
  92. }
  93. if((tr - tl + 1) & 1) {
  94. return 0;
  95. }
  96. int tm = (tl + tr) >> 1;
  97. int m = (l + r) >> 1;
  98. return equals(tl, tm, l, m) && equals(tm + 1, tr, m + 1, r) || equals(tl, tm, m + 1, r) && equals(tm + 1, tr, l, m);
  99. }
  100.  
  101. signed main() {
  102. seriy();
  103. cin >> s >> t;
  104. pows[0] = 1;
  105. for(int i = 1; i < MAXN; i++) {
  106. pows[i] = pows[i - 1] * BASE;
  107. pows[i] %= MOD;
  108. }
  109. sh = get_hash(s);
  110. th = get_hash(t);
  111. cout << ((equals(0, s.size() - 1, 0, t.size() - 1)) ? "YES" : "NO");
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment