Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- template<int MOD, int M>
- struct THash {
- int n;
- vector<ll> pwr;
- vector<ll> arr;
- THash(const string& s) {
- n = size(s);
- pwr.assign(n + 1, 1);
- for (int i = 1; i <= n; i++) {
- pwr[i] = pwr[i - 1] * M % MOD;
- }
- arr.assign(n, 0);
- for (int i = 0; i < n; i++) {
- arr[i] = s[i];
- if (i) {
- arr[i] += arr[i - 1] * M;
- arr[i] %= MOD;
- }
- }
- }
- ll operator ()(int l, int r) const {
- if (l > r) return 0;
- int len = r - l + 1;
- ll result = arr[r] - (l > 0 ? arr[l - 1] * pwr[len] % MOD : 0);
- return (result + MOD) % MOD;
- }
- };
- int main() {
- const int MOD = 1e9 + 7;
- const int M = 3301;
- string a, b;
- cin >> a >> b;
- const int n = size(a);
- const int m = size(b);
- if (n != m) {
- cout << "NO\n";
- return 0;
- }
- if (n == 0) {
- cout << "YES\n";
- return 0;
- }
- THash<MOD, M> arr(a);
- THash<MOD, M> brr(b);
- int ans = 0;
- for (int i = 0; i < n; i++) {
- if (arr(i, n - 1) == brr(0, n - 1 - i) && arr(0, i - 1) == brr(n - i, n - 1)) {
- ans++;
- }
- }
- cout << ans << endl;
- if (ans > 0) {
- cout << "YES\n";
- } else {
- cout << "NO\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement