#include "dna.h" #include<bits/stdc++.h> using namespace std; int pref[100002][3][3]; int apa(char a){ if(a=='A')return 0; if(a=='T')return 1; return 2; } void init(string a, string b) { a="."+a,b="."+b; for(int q=1;q<a.length();q++){ for(int w=0;w<3;w++){ for(int e=0;e<3;e++){ pref[q][w][e]=pref[q-1][w][e]; } } pref[q][apa(a[q])][apa(b[q])]++; //cout<<apa(a[q])<<" "<<apa(b[q])<<endl; } } int get_distance(int x, int y) { x++,y++; for(int q=0;q<3;q++){ int tot=0; for(int w=0;w<3;w++){ if(q==w)continue; tot+=(pref[y][q][w]-pref[x-1][q][w]); tot-=(pref[y][w][q]-pref[x-1][w][q]); } if(tot!=0)return -1; } int ans=0; int semua=0; for(int q=0;q<3;q++){ for(int w=q+1;w<3;w++){ int per=pref[y][q][w]-pref[x-1][q][w]; int dua=pref[y][w][q]-pref[x-1][w][q]; //cout<<per<<" "<<dua<<endl; ans+=min(per,dua); int apa=min(per,dua); per-=apa; dua-=apa; semua=max(semua,max(per,dua)); } } ans+=2*semua; return ans; }