#include #define MAX 1001000 char map(char c) { if(c == 'A') return 0; if(c == 'C') return 1; if(c == 'G') return 2; return 3; } void swap(char *str, int idx1, int idx2) { char h = str[idx1]; str[idx1] = str[idx2]; str[idx2] = h; } int main() { char strIn[MAX]; char strOut[MAX]; int count; fgets(strIn, MAX, stdin); fgets(strOut, MAX, stdin); count = strlen(strIn) - 1; for(int i = count - 1; i >= 0; i--) { strIn[i] = map(strIn[i]); strOut[i] = map(strOut[i]); } std::vector swapIdxs[4][4]; for(int i = count - 1; i >= 0; i--) { char from = strIn[i]; char to = strOut[i]; swapIdxs[from][to].push_back(i); } int swaps = 0; for(int i = 0; i < count; i++) { //printf("%s\n%s\n\n", strIn, strOut); if(strIn[i] == strOut[i]) continue; char from = strIn[i]; char to = strOut[i]; //printf("BBB %d %c %c\n", i, from+'0', to+'0'); if(swapIdxs[to][from].size() > 0) { //printf("AAA\n"); swaps++; int idx1 = swapIdxs[from][to].back(); int idx2 = swapIdxs[to][from].back(); swapIdxs[from][to].pop_back(); swapIdxs[to][from].pop_back(); swap(strIn, idx1, idx2); } else { for(int g = 0; g < 4; g++) { if(g == from) // dont swap A<=>A continue; if(swapIdxs[to][g].size() > 0) { swaps++; int idx1 = swapIdxs[from][to].back(); swapIdxs[from][to].pop_back(); int idx2 = swapIdxs[to][g].back(); swapIdxs[to][g].pop_back(); swapIdxs[from][g].push_back(idx2); swap(strIn, idx1, idx2); break; } } } } printf("%d", swaps); return 0; }