#include "bits/stdc++.h" #include "dna.h" // #include "grader.cpp" using namespace std; int p[100005][30], t[100005][30], A[100005][30][30]; string z = ".ATC"; void init(string a, string b) { for(int i = 0;i < (int)a.size();i++) { for(int j = 1; j <= 3; j++) { p[i + 1][j] += p[i][j] + (z[j] == a[i]); } } for(int i = 0; i < (int)b.size(); i++) { for(int j = 1; j <= 3; j++) { t[i + 1][j] += t[i][j] + (z[j] == b[i]); } } for(int i = 0; i < (int)a.size(); i++) { for(int j = 1; j <= 3; j++) { for(int k = 1; k <= 3; k++) { bool ok = (a[i] == z[j] && b[i] == z[k]); A[i + 1][j][k]+=A[i][j][k] + ok; } } } } int get_distance(int x, int y) { x++; y++; for(int i = 1; i <= 3; i++) { if(p[y][i] - p[x - 1][i] != t[y][i] - t[x - 1][i]) return -1; } int x1 = 0, x2 = 0; for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { // cout << i<< " " <<j << " " <<A[y][i][j] - A[x - 1][i][j] << '\n'; if(i == j) x1 += A[y][i][i] - A[x - 1][i][i]; else { x2 += min(A[y][i][j] - A[x-1][i][j],A[y][j][i] - A[x-1][j][i]); } } } int sz = (y - x + 1) - x1 - x2; return x2 / 2 + ((sz + 2) / 3 * 2); }