Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define D 50007
- #define step 67
- using namespace std;
- typedef unsigned long long ull;
- typedef ull arr[D];
- string s1, s2, s1rev;
- ull p[D], h1[D], h2[D], h1rev[D];
- ull get_hash(ull l, ull r, arr &h)
- {
- return h1[r] - h1[l-1];
- }
- int main()
- {
- cin >> s1 >> s2;
- if (s1.size() != s2.size())
- return cout << "No" << endl, 0;
- for (ull i = 0; i < s1.size(); i++)
- {
- s1[i] -= 60;
- s2[i] -= 60;
- }
- s1rev = s1;
- reverse(s1rev.begin(), s1rev.end());
- ull n = s1.size();
- s1 = ' ' + s1;
- s2 = ' ' + s2;
- s1rev = ' ' + s1rev;
- p[0] = 1;
- for (ull i = 1; i <= n + 1; i++)
- p[i] = p[i - 1] * step;
- for (ull i = 1; i <= n; i++)
- {
- h1[i] = h1[i - 1]*step + s1[i];
- h2[i] = h2[i - 1]*step + s2[i];
- h1rev[i] = h1rev[i]*step + s1rev[i];
- }
- for (ull i = 0; i <= n; i++)
- {
- ull hash1 = get_hash(i, n, h1) + get_hash(n-i-1, n, h1rev)*p[i+1];
- ull hash2 = h2[n]*p[i+1];
- if (hash1 == hash2)
- return cout << "Yes" << " " << i << endl, 0;
- }
- cout << "No" << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment