Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<vector>
- #include<math.h>
- #include<string>
- #include<sstream>
- #include<set>
- #include<map>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<memory.h>
- #include<ctime>
- #include<cassert>
- #include<limits.h>
- #include<unordered_map>
- #include<unordered_set>
- #define pb push_back
- #define sz(a) (int)a.size()
- #define bs binary_search
- #define np next_permutation
- #define mp make_pair
- #define all(a) a.begin(),a.end()
- #define read(a) scanf("%d", &a)
- #define writeln(a) printf("%d\n", a);
- #define forn(i, n) for (int i = 0; i < n; ++i)
- #define forv(i, v) for (int i = 0; i < sz(v); ++i)
- #define forsint(it, s) for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
- #define _(a, b) memset(a, b, sizeof a)
- #define pii pair<int, int>
- #define pll pair<long long, long long>
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
- template<class T> inline T sqr(T x) { return x * x; }
- const double pi = acos(-1.0), eps = 1e-9, e = exp(1.0);
- const int INF = 1000 * 1000 * 1000 + 7, MAXN = 100005, MOD = 1000000007, MAXBIT = 30;
- const ll INFL = 1e+18;
- void prepare(string s) {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt","w",stdout);
- #else
- if (sz(s) != 0) {
- freopen((s + ".in").c_str(), "r", stdin);
- freopen((s + ".out").c_str(), "w", stdout);
- }
- #endif
- }
- int n;
- string s, t;
- ll pp1[3*MAXN], pp2[3*MAXN], hs1[3*MAXN], hs2[3*MAXN], ht1[3*MAXN], ht2[3*MAXN];
- long long getHash1(int l, int r) {
- long long h = ht1[r];
- if (l > 0)
- h -= ht1[l - 1];
- h *= pp1[n - 1 - r];
- return h;
- }
- long long getHash1s(int l, int r) {
- long long h = hs1[r];
- if (l > 0)
- h -= hs1[l - 1];
- h *= pp1[n - 1 - r];
- return h;
- }
- long long getHash2(int l, int r) {
- long long h = ht2[r];
- if (l > 0)
- h = (h - ht2[l - 1] + INF) % INF;
- h = (h * pp2[n - 1 - r]) % INF;
- return h;
- }
- long long getHash2s(int l, int r) {
- long long h = hs2[r];
- if (l > 0)
- h = (h - hs2[l - 1] + INF) % INF;
- h = (h * pp2[n - 1 - r]) % INF;
- return h;
- }
- void solve()
- {
- cin >> n >> s >> t;
- if (sz(s) != sz(t)) {
- cout << -1;
- exit(0);
- }
- pp1[0] = pp2[0] = 1;
- for (int i = 1; i <= n; i++) {
- pp1[i] = pp1[i-1] * 53;
- pp2[i] = (pp2[i-1] * 53) % INF;
- }
- hs1[0] = s[0] - 'a' + 1;
- hs2[0] = (s[0] - 'a' + 1) % INF;
- ht1[0] = t[0] - 'a' + 1;
- ht2[0] = (t[0] - 'a' + 1) % INF;
- for (int i = 1; i < n; i++) {
- hs1[i] = hs1[i - 1] + pp1[i] * (s[i] - 'a' + 1);
- hs2[i] = (hs2[i - 1] + pp2[i] * (s[i] - 'a' + 1)) % INF;
- ht1[i] = ht1[i - 1] + pp1[i] * (t[i] - 'a' + 1);
- ht2[i] = (ht2[i - 1] + pp2[i] * (t[i] - 'a' + 1)) % INF;
- }
- for (int i = sz(t)-1; i >= 0; i--) {
- ll hashRight = getHash1(i, sz(t)-1);
- ll hashRight2 = getHash2(i, sz(t)-1);
- ll hashLeft = getHash1s(sz(t) - i, sz(t)-1);
- ll hashLeft2 = getHash2s(sz(t) - i, sz(t) - 1);
- if (hashRight == getHash1s(0, n - i - 1) && hashLeft == getHash1(0, i - 1)) {
- if (hashRight2 == getHash2s(0, n - i - 1) && hashLeft2 == getHash2(0, i - 1)) {
- cout << i;
- exit(0);
- }
- }
- }
- cout << -1;
- }
- int main()
- {
- prepare("");
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement