#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string a, b;
vector<map<pair<char, char>, int>> link;
vector<map<char, int>> dp1, dp2;
void init(std::string A, std::string B) {
a = A;
b = B;
dp1 = vector<map<char, int>>(a.size());
dp2 = vector<map<char, int>>(a.size());
link = vector<map<pair<char, char>, int>>(a.size());
for (int i = 0; i < a.size(); i++) {
if (i > 0) {
dp1[i] = dp1[i-1];
dp2[i] = dp2[i-1];
link[i] = link[i-1];
}
dp1[i][a[i]]++;
dp2[i][b[i]]++;
link[i][{a[i], b[i]}]++;
}
}
int get_distance(int x, int y) {
if (x != 0) {
if (!(
dp1[y]['A']-dp1[x-1]['A'] == dp2[y]['A']-dp2[x-1]['A'] &&
dp1[y]['C']-dp1[x-1]['C'] == dp2[y]['C']-dp2[x-1]['C'] &&
dp1[y]['T']-dp1[x-1]['T'] == dp2[y]['T']-dp2[x-1]['T']
))
return -1;
} else {
if (!(
dp1[y]['A'] == dp2[y]['A'] &&
dp1[y]['C'] == dp2[y]['C'] &&
dp1[y]['T'] == dp2[y]['T']
)) return -1;
}
int AC = link[y][{'A', 'C'}] - (x > 0? link[x-1][{'A', 'C'}] : 0);
int CA = link[y][{'C', 'A'}] - (x > 0? link[x-1][{'C', 'A'}] : 0);
int CT = link[y][{'C', 'T'}] - (x > 0? link[x-1][{'C', 'T'}] : 0);
int TC = link[y][{'T', 'C'}] - (x > 0? link[x-1][{'T', 'C'}] : 0);
int AT = link[y][{'A', 'T'}] - (x > 0? link[x-1][{'A', 'T'}] : 0);
int TA = link[y][{'T', 'A'}] - (x > 0? link[x-1][{'T', 'A'}] : 0);
int res = 0;
res += min(AC, CA)+min(CT, TC)+min(AT, TA);
AC -= min(AC, CA);
CA -= min(AC, CA);
AT -= min(AT, TA);
TA -= min(AT, TA);
CT -= min(CT, TC);
TC -= min(CT, TC);
if (AC+CA+AT+TA+CT+TC != 0) {
res += 2*(AC+CA+AT+TA+CT+TC)/3;
} else
res += (AC+CA+AT+TA+CT+TC)/2;
return res;
}
