Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <ctime>
- #include <cassert>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define all(v) v.begin(), v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #define ll long long
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- const ll base = 31;
- const ll base1 = 57;
- const int maxn = (int)1e6;
- const ll mod1 = (int)1e9 + 7;
- const ll inf = 9223372036854775807ll;
- vector<int> s, t;
- ll mhash[maxn], Pow[maxn], mhashr[maxn];
- ll mhash1[maxn], Pow1[maxn], mhashr1[maxn];
- char ss[maxn];
- map<pair<ll, ll>, int> Map;
- pair<ll, ll> mHash(int l, int r) {
- if (l > r) return mp(0, 0);
- ll hsh = mhash[r];
- if (l > 0) hsh -= Pow[r - l + 1] * mhash[l - 1];
- ll hsh1 = mhash1[r];
- if (l > 0) {
- hsh1 -= (Pow1[r - l + 1] * mhash1[l - 1]) % mod1;
- hsh1 = (hsh1 + mod1) % mod1;
- }
- return mp(hsh, hsh1);
- }
- pair<ll, ll> mHashr(int l, int r) {
- if (l > r) return mp(0, 0);
- ll hsh = mhashr[r];
- if (l > 0) hsh -= Pow[r - l + 1] * mhashr[l - 1];
- ll hsh1 = mhashr1[r];
- if (l > 0) {
- hsh1 -= (Pow1[r - l + 1] * mhashr1[l - 1]) % mod1;
- hsh1 = (hsh1 + mod1) % mod1;
- }
- return mp(hsh, hsh1);
- }
- ll modPow(ll a, ll n, ll mod = -1) {
- ll res = 1;
- while (n > 0) {
- if (n & 1) {
- res = res * a;
- if (mod != -1) res %= mod;
- }
- a = a * a;
- if (mod != -1) a %= mod;
- n >>= 1;
- }
- return res;
- }
- void First() {
- int mx = max(s.size() * 3, t.size() * 3);
- Pow[0] = Pow1[0] = 1;
- for (int i = 1; i <= mx + 1; ++i) {
- Pow[i] = Pow[i - 1] * base;
- Pow1[i] = (Pow1[i - 1] * base1) % mod1;
- }
- ll hsh = 0, hsh1 = 0;
- for (int i = 0; i < s.size(); ++i) {
- hsh = hsh * base + s[i];
- hsh1 = (hsh1 * base1 + s[i]) % mod1;
- }
- Map[mp(hsh, hsh1)] = 0;
- int n = s.size();
- for (int i = 1; i < n; ++i) {
- hsh -= s[i - 1] * Pow[n - 1];
- hsh = hsh * base + s[i - 1];
- hsh1 = (hsh1 - (s[i - 1] * Pow1[n - 1]) % mod1 + mod1) % mod1;
- hsh1 = (hsh1 * base1 + s[i - 1]) % mod1;
- Map[mp(hsh, hsh1)] = i;
- }
- int m = t.size();
- for (int i = 0; i < m; ++i)
- t.pb(t[i]);
- m += m;
- hsh = hsh1 = 0;
- for (int i = 0; i < m; ++i) {
- hsh = hsh * base + t[i];
- mhash[i] = hsh;
- hsh1 = (hsh1 * base1 + t[i]) % mod1;
- mhash1[i] = hsh1;
- }
- reverse(all(t));
- hsh = hsh1 = 0;
- for (int i = 0; i < m; ++i) {
- hsh = hsh * base + t[i];
- mhashr[i] = hsh;
- hsh1 = (hsh1 * base1 + t[i]) % mod1;
- mhashr1[i] = hsh1;
- }
- for (int i = 0; i < m / 2; ++i) {
- pair<ll, ll> hsh = mHashr(m - 1 - (i + n - 1), m - 1 - i);
- if (Map.count(hsh)) {
- int j = i + n, k = m / 2 - n + j - 1;
- if (mHash(j, k) == mHashr(m - 1 - k, m - 1 - j)) {
- puts("Yes");
- cout << Map[hsh] + 1 << " " << j % (m / 2) + 1 << endl;
- return;
- }
- }
- }
- puts("No");
- }
- void Second() {
- swap(s, t);
- int mx = max(s.size() * 3, t.size() * 3);
- Pow[0] = 1;
- Pow1[0] = 1;
- for (int i = 1; i <= mx + 1; ++i) {
- Pow[i] = Pow[i - 1] * base;
- Pow1[i] = (Pow1[i - 1] * base1) % mod1;
- }
- ll hsh = 0;
- ll hsh1 = 0;
- for (int i = (int)s.size() - 1; i >= 0; --i) {
- hsh = hsh * base + s[i];
- hsh1 = (hsh1 * base1 + s[i]) % mod1;
- }
- Map[mp(hsh, hsh1)] = 0;
- int n = s.size();
- for (int i = 1; i < n; ++i) {
- hsh = (hsh - s[i - 1]) * modPow(base, inf);
- hsh = hsh + Pow[n - 1] * s[i - 1];
- hsh1 = ((hsh1 - s[i - 1] + mod1) % mod1 * modPow(base1, mod1 - 2, mod1)) % mod1;
- hsh1 = (hsh1 + (Pow1[n - 1] * s[i - 1]) % mod1) % mod1;
- Map[mp(hsh, hsh1)] = i;
- }
- int m = t.size();
- for (int i = 0; i < m; ++i)
- t.pb(t[i]);
- m += m;
- hsh = hsh1 = 0;
- for (int i = 0; i < m; ++i) {
- hsh = hsh * base + t[i];
- hsh1 = (hsh1 * base1 + t[i]) % mod1;
- mhash[i] = hsh;
- mhash1[i] = hsh1;
- }
- reverse(all(t));
- hsh = hsh1 = 0;
- for (int i = 0; i < m; ++i) {
- hsh = hsh * base + t[i];
- mhashr[i] = hsh;
- hsh1 = (hsh1 * base1 + t[i]) % mod1;
- mhashr1[i] = hsh1;
- }
- for (int i = 0; i < m / 2; ++i) {
- pair<ll, ll> hsh = mHash(i, i + n - 1);
- if (Map.count(hsh)) {
- int j = i + n, k = m / 2 - n + j - 1;
- if (mHash(j, k) == mHashr(m - 1 - k, m - 1 - j)) {
- puts("Yes");
- cout << i + 1<< " " << Map[hsh] + 1 << endl;
- return;
- }
- }
- }
- puts("No");
- }
- int main() {
- #ifdef LOCAL
- freopen("in","r",stdin);
- freopen("out","w",stdout);
- #endif
- gets(ss);
- for (int i = 0; ss[i]; ++i)
- s.pb(ss[i] - 'a' + 1);
- gets(ss);
- for (int i = 0; ss[i]; ++i)
- t.pb(ss[i] - 'a' + 1);
- if (s.size() <= t.size()) First(); else
- Second();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment