#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; } char mapBack(char c) { if(c == 0) return 'A'; if(c == 1) return 'C'; if(c == 2) return 'G'; return 'T'; } 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); } //char strTest[MAX]; int swaps = 0; for(int i = 0; i < count; i++) { /*for(int i = 0; i < count; i++) strTest[i] = mapBack(strIn[i]); printf("%s\n", strTest);*/ char from = strIn[i]; char to = strOut[i]; if(from == to) continue; if(swapIdxs[to][from].size() > 0) { //printf("BBB\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); } } for(int i = 0; i < count; i++) { char from = strIn[i]; char to = strOut[i]; if(from == to) continue; for(int g = 0; g < 4; g++) { if(g == to) // 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; }