#include<bits/stdc++.h> #include "dna.h" using namespace std; int n; string a, b; static int c1[100005][3], c2[100005][3]; static int mis[100005][3][3]; string A, B; int id(char c) { if (c == 'A') return 0; if (c == 'T') return 1; return 2; } void init(string A, string B) { a = A; b = B; n = A.size(); for (int i = 0; i < n; i++) { for (int c = 0; c < 3; c++) { c1[i+1][c] = c1[i][c]; c2[i+1][c] = c2[i][c]; for (int d = 0; d < 3; d++) mis[i+1][c][d] = mis[i][c][d]; } c1[i+1][id(a[i])]++; c2[i+1][id(b[i])]++; if (a[i] != b[i]) mis[i+1][id(a[i])][id(b[i])]++; } } int get_distance(int x, int y) { int ca[3], cb[3]; for (int i = 0; i < 3; i++) { ca[i] = c1[y+1][i] - c1[x][i]; cb[i] = c2[y+1][i] - c2[x][i]; if (ca[i] != cb[i]) return -1; } int m[3][3] = {}; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) m[i][j] = mis[y+1][i][j] - mis[x][i][j]; int ans = 0; for (int i = 0; i < 3; i++) { for (int j = i+1; j < 3; j++) { int t = min(m[i][j], m[j][i]); ans += t; m[i][j] -= t; m[j][i] -= t; } } int rem = 0; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) rem += m[i][j]; ans += (rem / 3) * 2; return ans; }