#include "dna.h" #include <bits/stdc++.h> #define endl "\n" #define ff first #define ss second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; vector <int> pr[3][3]; vector <int> is1[3], is2[3]; map <char, int> m; void init(string a, string b) { m['A'] = 0, m['T'] = 1, m['C'] = 2; int n = a.size(); vector <int> x, y; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { pr[i][j].assign(n, 0); } is1[i].assign(n, 0); is2[i].assign(n, 0); } for (int i = 0; i < n; i++) { x.pb(m[a[i]]); y.pb(m[a[i]]); } for (int i = 0; i < n; i++) pr[x[i]][y[i]][i]++, is1[x[i]][i]++, is2[y[i]][i]++; for (int i = 1; i < n; i++) { for (int e = 0; e < 3; e++) { for (int e1 = 0; e1 < 3; e1++) pr[e][e1][i] += pr[e][e1][i-1]; is1[e][i] += is1[e][i-1]; is2[e][i] += is2[e][i-1]; } } } int get(char x, char y, int l, int r) { int res = pr[m[x]][m[y]][r]; if (l > 0) res -= pr[m[x]][m[y]][l-1]; return res; } int get_distance(int l, int r) { int at = get('A', 'T', l, r); int ta = get('T', 'A', l, r); int ac = get('A', 'C', l, r); int ca = get('C', 'A', l, r); int tc = get('T', 'C', l, r); int ct = get('C', 'T', l, r); int mn = min({at, tc, ca}); at -= mn; tc -= mn; ca -= mn; int res = mn * 2; mn = min({ta, ac, ct}); res += mn * 2; ta -= mn; ac -= mn; ct -= mn; if (at != ta || tc != ct || ac != ca) { return -1; } res += at + ct + ac; return res; }