Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define double long double
- #define For(i,z) for(int i=0;i<z;i++)
- #define ex(a) {cout << a; exit(0);}
- using namespace std;
- const int N = 5e3+5;
- const int INF = 1e12;
- const double PI = 3.1415926535897932384626433832795;
- const int MOD = 1e9+9;
- int need;
- int n;
- int hs[N];
- int rev[N];
- int mult[N];
- string fr, to;
- bool check(int k)
- {
- int lef = (hs[n-1] - hs[k-1] + MOD) % MOD; // : mult[k]
- int rig = (rev[n-1] - rev[n-1-k] + MOD) % MOD;
- int cur = (lef + rig * mult[k]) % MOD;
- int sec = need * mult[k] % MOD;
- //cout << k << " : " << cur << ' ' << sec << endl;
- return (cur == sec);
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- mult[0] = 1;
- For (i, N-1) mult[i+1] = mult[i] * 101 % MOD;
- cin >> fr >> to;
- if (fr.size() != to.size()) ex("No\n")
- if (to == fr) ex("Yes\n0")
- hs[0] = fr[0] - 'A'+1;
- n = fr.size();
- For (i, n-1) hs[i+1] = (hs[i] + (fr[i+1]-'A'+1)*mult[i+1]) % MOD;
- For (i, n) need += (to[i]-'A'+1)*mult[i], need %= MOD;
- rev[0] = fr[n-1]-'A'+1;
- For (i, n-1)
- rev[i+1] = (rev[i] + (fr[n-i-2] - 'A' + 1) * mult[i+1]) % MOD;
- For (i, n-1)
- if (check(i+1))
- {
- cout << "Yes\n" << i+1 << endl;
- return 0;
- }
- ex("No\n")
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement