Merge pull request algorithm-visualizer#191 from archie94/longestCommonSubsequence

TornjV · web-flow · commit c4d6f69e4d4b · 2016-06-22T09:31:34.000+02:00
Shortest Common Supersequence algorithm
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -18,11 +18,12 @@
          "fibonacci": "Fibonacci Sequence",
          "integer_partition": "Integer Partition",
          "knapsack_problem": "Knapsack Problem",
-         "longest_increasing_subsequence": "Longest Increasing Subsequence",
          "longest_common_subsequence": "Longest Common Subsequence",
+         "longest_increasing_subsequence": "Longest Increasing Subsequence",
          "max_subarray": "Maximum Subarray",
          "max_sum_path": "Maximum Sum Path",
          "pascal_triangle": "Pascal's Triangle",
+         "shortest_common_supersequence": "Shortest Common Supersequence",
          "sliding_window": "Sliding Window",
          "ugly_numbers": "Ugly Numbers"
       },
diff --git a/algorithm/dp/shortest_common_supersequence/basic/code.js b/algorithm/dp/shortest_common_supersequence/basic/code.js
@@ -0,0 +1,38 @@
+var i,j;
+
+// Fill memo table in bottom up manner 
+for ( i = 0; i <= m; i++ ) {
+	for ( j = 0; j <= n; j++ ) {
+		if( i === 0 ) {
+			A[i][j] = j;
+		} else if ( j === 0 ) {
+			A[i][j] = i;
+		} else if ( string1[i-1] == string2[j-1] ) {
+			tracer1._select ( i-1 )._wait ();
+ 			tracer2._select ( j-1 )._wait ();
+ 			tracer3._select ( i-1, j-1 )._wait ();
+
+			A[i][j] = A[i-1][j-1] + 1;
+
+			tracer1._deselect ( i-1 );
+ 			tracer2._deselect ( j-1 );
+ 			tracer3._deselect ( i-1, j-1 );
+		} else {
+			tracer3._select ( i-1, j )._wait ();
+ 			tracer3._select ( i, j-1 )._wait ();
+
+			if ( A[i-1][j] < A[i][j-1] ) {
+				A[i][j] = 1 + A[i-1][j];
+			} else {
+				A[i][j] = 1 + A[i][j-1];
+			}
+
+			tracer3._deselect ( i-1, j );
+ 			tracer3._deselect ( i, j-1 );
+		}
+		tracer3._notify ( i, j , A[i][j] )._wait ();
+ 		tracer3._denotify( i, j );
+	}
+}
+
+ logger._print ( 'Shortest Common Supersequence is ' + A[m][n] );
diff --git a/algorithm/dp/shortest_common_supersequence/basic/data.js b/algorithm/dp/shortest_common_supersequence/basic/data.js
@@ -0,0 +1,13 @@
+var string1 = 'AGGTAB';
+var string2 = 'GXTXAYB';
+var m = string1.length;
+var n = string2.length;
+var A = new Array (m+1);
+for (var i = 0; i < m+1; i++ ) {
+	A[i] = new Array (n+1);
+}
+
+var tracer1 = new Array1DTracer ( 'String 1')._setData ( string1 );
+var tracer2 = new Array1DTracer ( 'String 2')._setData ( string2 );
+var tracer3 = new Array2DTracer ( 'Memo Table')._setData ( A );
+var logger = new LogTracer ();
diff --git a/algorithm/dp/shortest_common_supersequence/desc.json b/algorithm/dp/shortest_common_supersequence/desc.json
@@ -0,0 +1,13 @@
+{
+  "Shortest Common Supersequence": "n computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if U is a supersequence of both X and Y. In other words, a shortest common supersequence of strings x and y is a shortest string z such that both x and y are subsequences of z." ,
+  "Complexity": {
+    "time": "O(mn)",
+    "space": "O(mn)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Shortest common supersequence"
+  }
+}
