#include "dna.h"
#include <string>
#include <cstdlib>
using namespace std;
int A[2][100005], C[2][100005], AC[100005], same[100005];
void init(string a, string b) {
int n = a.length();
for (int i = 0; i < n; i++) {
A[0][i + 1] = A[0][i];
A[1][i + 1] = A[1][i];
C[0][i + 1] = C[0][i];
C[1][i + 1] = C[1][i];
AC[i + 1] = AC[i];
same[i + 1] = same[i];
if (a[i] == 'A')
A[0][i + 1]++;
if (b[i] == 'A')
A[1][i + 1]++;
if (a[i] == 'C')
C[0][i + 1]++;
if (b[i] == 'C')
C[1][i + 1]++;
if (a[i] == 'A' && b[i] == 'C')
AC[i + 1]++;
if (a[i] == 'C' && b[i] == 'A')
AC[i + 1]--;
if (a[i] == b[i])
same[i + 1]++;
}
}
int get_distance(int x, int y) {
if ((A[0][y + 1] - A[0][x] != A[1][y + 1] - A[1][x]) || (C[0][y + 1] - C[0][x] != C[1][y + 1] - C[1][x]))
return -1;
return ((y - x + 1) - (same[y + 1] - same[x]) + abs(AC[y + 1] - AC[x])) / 2;
}
