String Tale

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define SZ(x) ((int)x.size())

const ll MOD = 1000000007;

bool U[205];
int N;
ll E1[250005], E2[250005], LH1[250005], LH2[250005], RH1[250005], RH2[250005];
string S, T;
vector<int> P;

bool calcHashes(ll p1, ll p2)
{
    E1[1] = p1, E2[1] = p2;
    f(i,2,N)
    {
        E1[i] = (E1[i-1]*p1) % MOD;
        E2[i] = (E2[i-1]*p2) % MOD;
        if(E1[i] == 0 || E2[i] == 0) return false;
    }
    LH1[0] = LH2[0] = S[0];
    f(i,1,N-1)
    {
        LH1[i] = (LH1[i-1]*p1 + S[i]) % MOD;
        if(LH1[i] == 0) return false;
    }
    f(i,1,N-1)
    {
        LH2[i] = (LH2[i-1]*p2 + S[i]) % MOD;
        if(LH2[i] == 0) return false;
    }
    ll mult1 = 1, mult2 = 1;
    RH1[N-1] = RH2[N-1] = S[N-1];
    fd(i,N-2,0)
    {
        mult1 = (mult1*p1) % MOD;
        mult2 = (mult2*p2) % MOD;
        RH1[i] = (RH1[i+1] + S[i]*mult1) % MOD;
        RH2[i] = (RH2[i+1] + S[i]*mult2) % MOD;
        if(RH1[i] == 0 || RH2[i] == 0) return false;
    }
    return true;
}

int main()
{
    f(i,2,200) if(!U[i])
    {
        if(i > 30) P.pb(i);
        for(int k = i; k <= 200; k += i) U[k] = true;
    }
    cin >> N >> S >> T;
    ll p1 = 31, p2 = 37;
    while(true)
    {
        int idx1 = rand() % SZ(P);
        int idx2 = rand() % SZ(P);
        if(idx1 == idx2) continue;
        if(calcHashes(P[idx1],P[idx2]))
        {
            p1 = P[idx1];
            p2 = P[idx2];
            break;
        }
    }
    ll h1 = T[0];
    ll h2 = T[0];
    f(i,1,N-1) h1 = (h1*p1 + T[i]) % MOD;
    f(i,1,N-1) h2 = (h2*p2 + T[i]) % MOD;
    if(h1 == LH1[N-1] && h2 == LH2[N-1])
    {
        cout << 0;
        return 0;
    }
    f(i,0,N-2)
    {
        ll hash1 = (RH1[i+1]*E1[i+1] + LH1[i]) % MOD;
        ll hash2 = (RH2[i+1]*E2[i+1] + LH2[i]) % MOD;
        if(hash1 == h1 && hash2 == h2)
        {
            cout << N-i-1;
            return 0;
        }
    }
    cout << -1;
}