#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> a1, a2, c1, c2, t1, t2, at, ta, ct, tc, ac, ca;
void init(string a, string b) {
int n = a.size();
a1.resize(n+1, 0);
c1.resize(n+1, 0);
t1.resize(n+1, 0);
a2.resize(n+1, 0);
c2.resize(n+1, 0);
t2.resize(n+1, 0);
at.resize(n+1, 0);
ta.resize(n+1, 0);
ca.resize(n+1, 0);
ac.resize(n+1, 0);
tc.resize(n+1, 0);
ct.resize(n+1, 0);
for (int i=0; i<n; ++i){
a1[i+1] = a1[i];
c1[i+1] = c1[i];
t1[i+1] = t1[i];
a2[i+1] = a2[i];
c2[i+1] = c2[i];
t2[i+1] = t2[i];
at[i+1] = at[i];
ta[i+1] = ta[i];
ac[i+1] = ac[i];
ca[i+1] = ca[i];
tc[i+1] = tc[i];
ct[i+1] = ct[i];
if (a[i]==b[i]){
continue;
}
if (a[i]=='T' && b[i]=='C'){
++tc[i+1];
++t1[i+1];
++c2[i+1];
}
else if (a[i]=='T' && b[i]=='A'){
++ta[i+1];
++t1[i+1];
++a2[i+1];
}
else if (a[i]=='C' && b[i]=='T'){
++ct[i+1];
++c1[i+1];
++t2[i+1];
}
else if (a[i]=='C' && b[i]=='A'){
++ca[i+1];
++c1[i+1];
++a2[i+1];
}
else if (a[i]=='A' && b[i]=='C'){
++ac[i+1];
++a1[i+1];
++c2[i+1];
}
else if (a[i]=='A' && b[i]=='T'){
++at[i+1];
++a1[i+1];
++t2[i+1];
}
}
}
int get_distance(int x, int y) {
int TC = tc[y+1]-tc[x], CT=ct[y+1]-ct[x], TA=ta[y+1]-ta[x], AT=at[y+1]-at[x], AC=ac[y+1]-ac[x], CA=ca[y+1]-ca[x];
int A1 = a1[y+1]-a1[x], A2 = a2[y+1]-a2[x], T1=t1[y+1]-t1[x], T2=t2[y+1]-t2[x], C1=c1[y+1]-c1[x], C2=c2[y+1]-c2[x];
if (A1!=A2 || T1!=T2 || C1!=C2){
return -1;
}
int val = abs(TC-CT)+abs(TA-AT)+abs(AC-CA);
val*=2;
val/=3;
val+=min(TC, CT)+min(TA, AT)+min(AC, CA);
return val;
}
