#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, l, r) for(int i = l; i <= r; i++) #define FORD(i, l, r) for(int i = l; i >= r; i--) const int N = 1e5 + 5; int prefa_a[N], prefa_c[N], prefa_t[N]; int prefb_a[N], prefb_c[N], prefb_t[N]; int diff[N][3][3]; string a, b; int n; int get_id(char c){ if(c == 'A') return 0; if(c == 'C') return 1; return 2; } void init(string __a, string __b){ a = __a; b = __b; n = a.size(); a = ' ' + a; b = ' ' + b; FOR(i, 1, n){ prefa_a[i] = prefa_a[i - 1] + (a[i] == 'A'); prefa_c[i] = prefa_c[i - 1] + (a[i] == 'C'); prefa_t[i] = prefa_t[i - 1] + (a[i] == 'T'); prefb_a[i] = prefb_a[i - 1] + (b[i] == 'A'); prefb_c[i] = prefb_c[i - 1] + (b[i] == 'C'); prefb_t[i] = prefb_t[i - 1] + (b[i] == 'T'); int idx1 = get_id(a[i]), idx2 = get_id(b[i]); FOR(id1, 0, 2)FOR(id2, 0, 2){ diff[i][id1][id2] = diff[i - 1][id1][id2]; } diff[i][idx1][idx2] += 1; } } int geta_a(int l, int r){ return prefa_a[r] - prefa_a[l - 1]; } int geta_c(int l, int r){ return prefa_c[r] - prefa_c[l - 1]; } int geta_t(int l, int r){ return prefa_t[r] - prefa_t[l - 1]; } int getb_a(int l, int r){ return prefb_a[r] - prefb_a[l - 1]; } int getb_c(int l, int r){ return prefb_c[r] - prefb_c[l - 1]; } int getb_t(int l, int r){ return prefb_t[r] - prefb_t[l - 1]; } //0 -> A, 1 -> C, 2 -> T int get_distance(int l, int r){ ++l; ++r; if(geta_a(l, r) == getb_a(l, r) && geta_c(l, r) == getb_c(l, r) && geta_t(l, r) == getb_t(l, r)){ int ac = diff[r][0][1] - diff[l - 1][0][1]; int at = diff[r][0][2] - diff[l - 1][0][2]; int ca = diff[r][1][0] - diff[l - 1][1][0]; int ct = diff[r][1][2] - diff[l - 1][1][2]; int ta = diff[r][2][0] - diff[l - 1][2][0]; int tc = diff[r][2][1] - diff[l - 1][2][1]; int ans = 0; int t; //mis of A T t = min(at, ta); ans += t; at -= t; ta -= t; //mis of A C t = min(ac, ca); ans += t; ac -= t; ca -= t; // mis of C T t = min(tc, ct); ans += t; tc -= t; ct -= t; int old = ans; //cerr << "AFTER 1 CYCLE:\n" << at << " " << ta << " " << ac << " " << ca << " " << tc << " " << ct << "\n"; //now AC - CT - TA, take 2 ans += 2 * (ac + ct + ta) / 3; //AT - TC - CA if(ans == old) ans += 2 * (at + tc + ca) / 3; //CT - TA - AC if(ans == old) ans += 2 * (ct + ta + ac) / 3; return ans; } else return -1; }/* signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); string __a, __b; cin >> __a >> __b; init(__a, __b); int q; int case_cnt = 1; cin >> q; while(q--){ int l, r; cin >> l >> r; cout << "Case " << case_cnt++ << ": " << get_distance(l, r) << "\n"; } return 0; }*/