#include "dna.h"
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
string a, b;
int n;
vector<int> prefix_a[3]; // 1 - based
vector<int> prefix_b[3]; // 1 - based
vector<int> prefix_dif; // 1 - based
enum Nucleotide
{
A,
T,
C
};
void init(string _a, string _b)
{
a = _a;
b = _b;
n = a.size();
for (int i = 0; i < 3; i++)
{
prefix_a[i] = vector<int>(n + 1, 0);
prefix_b[i] = vector<int>(n + 1, 0);
prefix_dif.resize(n + 1, 0);
}
string letters = "ATC";
map<char, int> freq_a, freq_b;
for (int i = 1; i <= n; i++)
{
freq_a[a[i - 1]]++;
freq_b[b[i - 1]]++;
prefix_dif[i] = (a[i - 1] != b[i - 1]) + prefix_dif[i - 1];
for (int j = 0; j < 3; j++)
{
char letter = letters[j];
prefix_a[j][i] = freq_a[letter];
prefix_b[j][i] = freq_b[letter];
}
}
}
int count_letter(int letter, int i, int j, char str)
{
// i, j are 0-based
i++;
j++;
vector<int> &prefix = (str == 'a' ? prefix_a[letter] : prefix_b[letter]);
return prefix[j] - prefix[i - 1];
}
int get_distance(int x, int y)
{
// substrings are only composed of 'A' and 'T'
vector<int> letter_count_a(3), letter_count_b(3);
for (int letter = 0; letter < 3; letter++)
{
letter_count_a[letter] = count_letter(letter, x, y, 'a');
letter_count_b[letter] = count_letter(letter, x, y, 'b');
if (letter_count_a[letter] != letter_count_b[letter])
return -1;
}
// counts are good
int dif = prefix_dif[y + 1] - prefix_dif[x]; // prefix_dif is 1 based
return dif / 2;
}
