#include "dna.h"
#include <vector>
using namespace std;
static string C = "ATC";
static vector<int> cnt[3][3];
void init(string a, string b) {
int N = a.length();
for(int k = 0; k < 9; k++) cnt[k/3][k%3].resize(N+1, 0);
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
for(int i = 0; i < N; i++)
cnt[j][k][i+1] = (a[i] == C[j] && b[i] == C[k]);
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
for(int i = 0; i < N; i++)
cnt[j][k][i+1] += cnt[j][k][i];
}
int get_distance(int x, int y) {
int cnt_sub[3][3];
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
cnt_sub[j][k] = cnt[j][k][y+1] - cnt[j][k][x];
for(int i = 0; i < 3; i++) {
int d = 0;
for(int j = 0; j < 3; j++) d += cnt_sub[i][j];
for(int j = 0; j < 3; j++) d -= cnt_sub[j][i];
if(d) return -1;
}
cnt_sub[0][0] = cnt_sub[1][1] = cnt_sub[2][2] = 0;
int ret = 0;
for(int i = 0; i < 9; i++) {
int m = min(cnt_sub[i/3][i%3], cnt_sub[i%3][i/3]);
ret += m;
cnt_sub[i/3][i%3] -= m;
cnt_sub[i%3][i/3] -= m;
}
int s = 0;
for(int i = 0; i < 9; i++) s += cnt_sub[i/3][i%3];
ret += s/3*2;
return ret;
}
