Advertisement
999ms

THash<MOD, M>

Apr 2nd, 2020
523
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. template<int MOD, int M>
  6. struct THash {
  7.   int n;
  8.   vector<ll> pwr;
  9.   vector<ll> arr;
  10.   THash(const string& s) {
  11.     n = size(s);
  12.     pwr.assign(n + 1, 1);
  13.     for (int i = 1; i <= n; i++) {
  14.       pwr[i] = pwr[i - 1] * M % MOD;
  15.     }
  16.     arr.assign(n, 0);
  17.     for (int i = 0; i < n; i++) {
  18.       arr[i] = s[i];
  19.       if (i) {
  20.         arr[i] += arr[i - 1] * M;
  21.         arr[i] %= MOD;
  22.       }
  23.     }
  24.   }
  25.   ll operator ()(int l, int r) const {
  26.     if (l > r) return 0;
  27.     int len = r - l + 1;
  28.     ll result = arr[r] - (l > 0 ? arr[l - 1] * pwr[len] % MOD : 0);
  29.     return (result + MOD) % MOD;
  30.   }
  31. };
  32.  
  33. int main() {
  34.   const int MOD = 1e9 + 7;
  35.   const int M = 3301;
  36.   string a, b;
  37.   cin >> a >> b;
  38.   const int n = size(a);
  39.   const int m = size(b);
  40.   if (n != m) {
  41.     cout << "NO\n";
  42.     return 0;
  43.   }
  44.   if (n == 0) {
  45.     cout << "YES\n";
  46.     return 0;
  47.   }
  48.   THash<MOD, M> arr(a);
  49.   THash<MOD, M> brr(b);
  50.   int ans = 0;
  51.   for (int i = 0; i < n; i++) {
  52.     if (arr(i, n - 1) == brr(0, n - 1 - i) && arr(0, i - 1) == brr(n - i, n - 1)) {
  53.       ans++;
  54.     }
  55.   }
  56.   cout << ans << endl;
  57.   if (ans > 0) {
  58.     cout << "YES\n";
  59.   } else {
  60.     cout << "NO\n";
  61.   }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement