npcoder2k14
diff --git a/‎edit_distance_backtracking.cpp‎
Lines changed: 165 additions & 0 deletions b/‎edit_distance_backtracking.cpp‎
Lines changed: 165 additions & 0 deletions
@@ -0,0 +1,165 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+
+class Alignment {
+
+	string sx, sy, sa, sb;
+
+	vector<vector<int> > A;
+	int sxL, syL;
+	int cost = 0;
+
+	//insertion cost
+	inline int insC() {
+		return 4;
+	}
+
+	//deletion cost
+	inline int delC() {
+		return 4;
+	}
+
+	//modification cost
+	inline int modC(char fr, char to) {
+		if(fr == to)
+			return 0;
+		return 3;
+	}
+
+public:
+
+	//constructor
+	Alignment(string s1, string s2) : sx(s1), sy(s2),
+				sxL(s1.length()), syL(s2.length())
+	{	
+		//allocating size to array needed
+		A.resize(s2.length()+4, vector<int>(s1.length()+4, 0));
+	}
+
+	//recurrence
+	int rec(int i, int j) {
+		return min(modC(sx[i-1], sy[j-1]) + A[i-1][j-1], min(delC() + A[i-1][j], insC() + A[i][j-1]));
+		//i-1, j-1 in sx, sy b/c of 0-indexing in string
+	}
+
+	//building array of cost
+	void form_array() {
+
+		//initialising the base needed in dp
+		//building up the first column, consider taking first string sx and second as null
+		for(int i = 0; i <= sxL; i++) {
+			A[i][0] = i*(delC());
+		}
+
+		//building up the first row, consider taking first string null and second as string sy
+		for(int i = 0; i <= syL; i++) {
+			A[0][i] = i*(insC());
+		}
+
+		//building up whole array from previously known values
+		for(int i = 1; i <= sxL; i++) {
+			for(int j = 1; j <= syL; j++) {
+
+				A[i][j] = rec(i, j);
+			}
+		}
+
+		cost = A[sxL][syL];
+
+	}
+
+	//finding the alignment
+	void trace_back(int i, int j) {
+
+		while(true) {
+			if(i == 0 || j == 0) {
+				break;
+			}
+			//A[i][j] will have one of the three above values from which it is derived 
+			//so comapring from each one
+			if(i >= 0 && j >= 0 && rec(i, j) == modC(sx[i-1], sy[j-1]) + A[i-1][j-1]) {
+				sa.push_back(sx[i-1]);
+				sb.push_back(sy[j-1]);
+				i--, j--;
+			}
+
+			else if((i-1) >= 0 && j >= 0 && rec(i, j) == delC() + A[i-1][j]) {
+				sa.push_back(sx[i-1]);        //0-indexing of string
+				sb.push_back('-');
+				i -= 1;
+			}
+
+			else if(i >= 0 && (j-1) >= 0){
+				sa.push_back('-');        //0-indexing of string
+				sb.push_back(sy[j-1]);	
+				j -= 1;
+			}
+		}
+
+		if(i != 0) {
+			while(i) {
+				sa.push_back(sx[i-1]);
+				sb.push_back('-');
+				i--;
+			}
+		}
+
+		else {
+			while(j) {
+				sa.push_back('-');
+				sb.push_back(sy[j-1]);
+				j--;
+			}
+		}
+	}
+
+	//returning the alignment
+	pair<string, string> alignst() {
+		//reversing the alignments because we have formed the 
+		//alignments from backward(see: trace_back, i, j started from m, n respectively)
+		reverse(sa.begin(), sa.end());
+		reverse(sb.begin(), sb.end());
+		return make_pair(sa, sb);
+	}
+
+
+	//returning the cost
+	int kyc() { return cost;}
+};
+
+int main() {
+
+
+	//converting sx to sy
+	string sx, sy;
+	sx = "GCCCTAGCG";
+	sy = "GCGCAATG";
+
+	//standard input stream
+	//cin >> sx >> sy;
+
+	pair<string, string> st;
+
+	Alignment dyn(sx, sy);
+	dyn.form_array();
+	dyn.trace_back(sx.length(), sy.length());
+	st = dyn.alignst();
+	//Alignments can be different for same strings but cost will be same
+
+	cout << "Alignments of the strings\n";
+	cout << st.first << "\n";
+	cout << st.second << "\n";
+	cout << "Cost associated = ";
+	cout << dyn.kyc() << "\n";
+
+	/*	Alignments
+	M - modification, D - deletion, I - insertion for converting string1 to string2
+
+			     M M MD
+	string1	-  GCCCTAGCG
+	string2 -  GCGCAAT-G
+
+	*/
+
+}