#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define all(a) a.begin(), a.end()
#define pb push_back
int N = 0;
vector<int> a_prefix, c_prefix, t_prefix;
vector<int> a_prefix1, c_prefix1, t_prefix1;
vector<int> same;
void init(std::string a, std::string b) {
N = a.size();
a_prefix.resize(N);c_prefix.resize(N);t_prefix.resize(N);
a_prefix1.resize(N);c_prefix1.resize(N);t_prefix1.resize(N);
if (a[0] == 'A') a_prefix[0] = 1;
if (a[0] == 'C') c_prefix[0] = 1;
if (a[0] == 'T') t_prefix[0] = 1;
if (b[0] == 'A') a_prefix1[0] = 1;
if (b[0] == 'C') c_prefix1[0] = 1;
if (b[0] == 'T') t_prefix1[0] = 1;
FOR(i,1,N){
a_prefix[i] = a_prefix[i-1];c_prefix[i] = c_prefix[i-1];t_prefix[i] = t_prefix[i-1];
if (a[i] == 'A') a_prefix[i]++;
if (a[i] == 'C') c_prefix[i]++;
if (a[i] == 'T') t_prefix[i]++;
a_prefix1[i] = a_prefix1[i-1];c_prefix1[i] = c_prefix1[i-1];t_prefix1[i] = t_prefix1[i-1];
if (b[i] == 'A') a_prefix1[i]++;
if (b[i] == 'C') c_prefix1[i]++;
if (b[i] == 'T') t_prefix1[i]++;
}
same.resize(N);
if (a[0] != b[0]) same[0] = 1;
FOR(i,1,N){
same[i] = same[i-1];
if (a[i] != b[i]) same[i]++;
}
}
int get_distance(int x, int y) {
int a_count = a_prefix[y], c_count = c_prefix[y], t_count = t_prefix[y];
int a_count1 = a_prefix1[y], c_count1 = c_prefix1[y], t_count1 = t_prefix1[y];
if (x){
a_count -= a_prefix[x-1];c_count -= c_prefix[x-1];t_count -= t_prefix[x-1];
a_count1 -= a_prefix1[x-1]; c_count1 -= c_prefix1[x-1]; t_count1 -= t_prefix1[x-1];
}
if (a_count-a_count1 == 0 && c_count-c_count1 == 0 && t_count-t_count1 == 0){
int o = same[y];
if (x) o -= same[x-1];
return (o+1)/2;
}
return -1;
}
