#include "dna.h" #include <bits/stdc++.h> using namespace std; string all = "ACT"; vector<int> A; vector<int> C; vector<int> T; map<pair<char, char>, vector<int>> m; void init(std::string a, std::string b){ A.resize(a.size()+1); C.resize(a.size()+1); T.resize(a.size()+1); for(int i = 0; i < all.size(); i++){ for(int y = 0; y < all.size(); y++){ m[{all[i], all[y]}].resize(a.size()+1, 0); } } for(int i = 1; i <= a.size(); i++){ if(a[i-1] == 'A'){ A[i]++; }else if(a[i-1] == 'C'){ C[i]++; }else{ T[i]++; } if(b[i-1] == 'A'){ A[i]--; }else if(b[i-1] == 'C'){ C[i]--; }else{ T[i]--; } A[i] += A[i-1]; C[i] += C[i-1]; T[i] += T[i-1]; m[{a[i-1], b[i-1]}][i]++; for(int z = 0; z < all.size(); z++){ for(int y = 0; y < all.size(); y++){ m[{all[z], all[y]}][i] += m[{all[z], all[y]}][i-1]; } } } } int get_distance(int x, int y){ x++; y++; if(!(A[y] - A[x-1] == 0 && C[y] - C[x-1] == 0 && T[y] - T[x-1] == 0)){ return -1; } int ans = 0; int cur = y-x+1; cur -= m[{'A', 'A'}][y] - m[{'A', 'A'}][x-1]; cur -= m[{'T', 'T'}][y] - m[{'T', 'T'}][x-1]; cur -= m[{'C', 'C'}][y] - m[{'C', 'C'}][x-1]; for(int i = 0; i < all.size(); i++){ for(int y = i+1; y < all.size(); y++){ ans += min(m[{all[i], all[y]}][y] - m[{all[i], all[y]}][x-1], m[{all[y], all[i]}][y] - m[{all[y], all[i]}][x-1]); cur -= 2*min(m[{all[i], all[y]}][y] - m[{all[i], all[y]}][x-1], m[{all[y], all[i]}][y] - m[{all[y], all[i]}][x-1]); } } ans += cur/3*2; return ans; }