GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Merge pull request #191 from archie94/longestCommonSubsequence · tangjun1990/AlgorithmVisualizer@c4d6f69

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • dp/shortest_common_supersequence
      • basic
        • code.js
        • data.js
      • desc.json
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,12 @@
1818
"fibonacci": "Fibonacci Sequence",
1919
"integer_partition": "Integer Partition",
2020
"knapsack_problem": "Knapsack Problem",
21-
"longest_increasing_subsequence": "Longest Increasing Subsequence",
2221
"longest_common_subsequence": "Longest Common Subsequence",
22+
"longest_increasing_subsequence": "Longest Increasing Subsequence",
2323
"max_subarray": "Maximum Subarray",
2424
"max_sum_path": "Maximum Sum Path",
2525
"pascal_triangle": "Pascal's Triangle",
26+
"shortest_common_supersequence": "Shortest Common Supersequence",
2627
"sliding_window": "Sliding Window",
2728
"ugly_numbers": "Ugly Numbers"
2829
},
Collapse file

‎algorithm/dp/shortest_common_supersequence/basic/code.js‎

Copy file name to clipboard
+38Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
var i,j;
2+
3+
// Fill memo table in bottom up manner
4+
for ( i = 0; i <= m; i++ ) {
5+
for ( j = 0; j <= n; j++ ) {
6+
if( i === 0 ) {
7+
A[i][j] = j;
8+
} else if ( j === 0 ) {
9+
A[i][j] = i;
10+
} else if ( string1[i-1] == string2[j-1] ) {
11+
tracer1._select ( i-1 )._wait ();
12+
tracer2._select ( j-1 )._wait ();
13+
tracer3._select ( i-1, j-1 )._wait ();
14+
15+
A[i][j] = A[i-1][j-1] + 1;
16+
17+
tracer1._deselect ( i-1 );
18+
tracer2._deselect ( j-1 );
19+
tracer3._deselect ( i-1, j-1 );
20+
} else {
21+
tracer3._select ( i-1, j )._wait ();
22+
tracer3._select ( i, j-1 )._wait ();
23+
24+
if ( A[i-1][j] < A[i][j-1] ) {
25+
A[i][j] = 1 + A[i-1][j];
26+
} else {
27+
A[i][j] = 1 + A[i][j-1];
28+
}
29+
30+
tracer3._deselect ( i-1, j );
31+
tracer3._deselect ( i, j-1 );
32+
}
33+
tracer3._notify ( i, j , A[i][j] )._wait ();
34+
tracer3._denotify( i, j );
35+
}
36+
}
37+
38+
logger._print ( 'Shortest Common Supersequence is ' + A[m][n] );
Collapse file

‎algorithm/dp/shortest_common_supersequence/basic/data.js‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
var string1 = 'AGGTAB';
2+
var string2 = 'GXTXAYB';
3+
var m = string1.length;
4+
var n = string2.length;
5+
var A = new Array (m+1);
6+
for (var i = 0; i < m+1; i++ ) {
7+
A[i] = new Array (n+1);
8+
}
9+
10+
var tracer1 = new Array1DTracer ( 'String 1')._setData ( string1 );
11+
var tracer2 = new Array1DTracer ( 'String 2')._setData ( string2 );
12+
var tracer3 = new Array2DTracer ( 'Memo Table')._setData ( A );
13+
var logger = new LogTracer ();
Collapse file

‎algorithm/dp/shortest_common_supersequence/desc.json‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"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." ,
3+
"Complexity": {
4+
"time": "O(mn)",
5+
"space": "O(mn)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Shortest common supersequence"
12+
}
13+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.