Created
March 18, 2015 12:04
-
-
Save vishnujayvel/4dbdc815019ed00cadb4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <list> | |
#include <map> | |
#include <set> | |
#include <deque> | |
#include <queue> | |
#include <stack> | |
#include <bitset> | |
#include <algorithm> | |
#include <functional> | |
#include <numeric> | |
#include <utility> | |
#include <sstream> | |
#include <iostream> | |
#include <iomanip> | |
#include <cstdio> | |
#include <cmath> | |
#include <cstdlib> | |
#include <ctime> | |
#include <cstring> | |
#include <climits> | |
#include <stdlib.h> | |
#include <stdio.h> | |
using namespace std; | |
#define REP(i,n) for(int i=0; i<n; i++) | |
#define FOR(i,st,end) for(int i=st;i<end;i++) | |
#define db(x) cout << (#x) << " = " << x << endl; | |
#define mp make_pair | |
#define pb push_back | |
#define MAX 100005 | |
typedef long long int ll; | |
int main(){ | |
int n; | |
string str1,str2; | |
cin>>n; | |
cin>>str1>>str2; | |
//This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index | |
//if sameIndex[0][1]=1 then it means 'a' from String S and 'b' from String T are in same index | |
//if sameIndex[1][0]=1 then it means 'b' from S and 'a' from T are in same index | |
int sameIndex[26][26]={0}; | |
//The below array is used to store the indexes of the mismatched characters in string T | |
//NOTE: String S and T are represented by str1 and str2 in the code and comments from now on | |
int match[26]; | |
int ham=0; | |
int f=0; | |
pair<int,int> ans; | |
memset(match,-1,sizeof match); | |
REP(i,n){ | |
sameIndex[str1[i]-'a'][str2[i]-'a']=1; | |
if(str1[i]!=str2[i]){ | |
match[str2[i]-'a']=i; | |
ham++; | |
} | |
} | |
REP(i,n){ | |
if(str1[i]!=str2[i]){ | |
//Case 1 | |
//If characters str1[i] and str2[i] are different | |
//check if character str2[i] in string str1 and str1[i] in string str2 are present in same index | |
//if present then the 2 characters can be swapped and thus hamming distance will be decremented by 2 | |
if(sameIndex[str2[i]-'a'][str1[i]-'a']){ | |
ham-=2; | |
f=1; | |
REP(j,n){ | |
if(str1[j]==str2[i]&&str2[j]==str1[i]){ | |
ans.first=i+1; | |
ans.second=j+1; | |
break; | |
} | |
} | |
break; | |
} | |
} | |
} | |
if(!f){ | |
REP(i,n){ | |
//Case 2 | |
//check if mismatched character belonging to str1 is present in mismatched character set of str2 | |
//if present then we can swap str1[i] with the index where str1[i] is present in str2 | |
if(str1[i]!=str2[i]){ | |
if(match[str1[i]-'a']!=-1){ | |
f=1; | |
ans.first=i+1; | |
ans.second=match[str1[i]-'a']+1; | |
ham--; | |
break; | |
} | |
} | |
} | |
} | |
cout<<ham<<endl; | |
if(f){ | |
cout<<ans.first<<" "<<ans.second<<endl; | |
} | |
else{ | |
cout<<"-1 -1"; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment