GeezerVison is showing github.com — Longest Common Subsequence · hhy5277/AlgorithmVisualizer@8ab9b80
File treeExpand file treeCollapse file tree Open diff view settings dp/longest_common_subsequence
Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboardExpand all lines: algorithm/category.json +6Lines changed: 6 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| 19 | 19 | "integer_partition": "Integer Partition", | 20 | 20 | "knapsack_problem": "Knapsack Problem", | 21 | 21 | "longest_increasing_subsequence": "Longest Increasing Subsequence", | | 22 | + "longest_common_subsequence": "Longest Common Subsequence", | 22 | 23 | "max_subarray": "Maximum Subarray", | 23 | 24 | "max_sum_path": "Maximum Sum Path", | 24 | 25 | "pascal_triangle": "Pascal's Triangle", | | 59 | 60 | "seive_of_erathrones": "Seive of Erathrones" | 60 | 61 | }, | 61 | 62 | "name": "Number Theory" | | 63 | + },"recursion": { | | 64 | + "list": { | | 65 | + "string_permutations": "String Permutations" | | 66 | + }, | | 67 | + "name": "Recursion" | 62 | 68 | }, | 63 | 69 | "search": { | 64 | 70 | "list": { | |
Collapse file Copy file name to clipboard +36Lines changed: 36 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +var i,j; | | 2 | + | | 3 | +// Build the memo table in bottom up fashion | | 4 | + for( i = 0; i <= m; i++ ) { | | 5 | + for( j = 0; j <= n; j++ ) { | | 6 | + if ( i === 0 || j === 0 ) { | | 7 | + A[i][j] = 0; | | 8 | + } else if ( string1[i-1] == string2[j-1] ) { | | 9 | + tracer1._select ( i-1 )._wait (); | | 10 | + tracer2._select ( j-1 )._wait (); | | 11 | + tracer3._select ( i-1, j-1 )._wait (); | | 12 | + | | 13 | + A[i][j] = A[i-1][j-1] + 1; | | 14 | + | | 15 | + tracer1._deselect ( i-1 ); | | 16 | + tracer2._deselect ( j-1 ); | | 17 | + tracer3._deselect ( i-1, j-1 ); | | 18 | + } else { | | 19 | + tracer3._select ( i-1, j )._wait (); | | 20 | + tracer3._select ( i, j-1 )._wait (); | | 21 | + | | 22 | + if( A[i-1][j] > A[i][j-1] ) { | | 23 | + A[i][j] = A[i-1][j]; | | 24 | + } else { | | 25 | + A[i][j] = A[i][j-1]; | | 26 | + } | | 27 | + | | 28 | + tracer3._deselect ( i-1, j ); | | 29 | + tracer3._deselect ( i, j-1 ); | | 30 | + } | | 31 | + tracer3._notify ( i, j , A[i][j] )._wait (); | | 32 | + tracer3._denotify( i, j ); | | 33 | + } | | 34 | + } | | 35 | + | | 36 | + logger._print ( 'Longest Common Subsequence is ' + A[m][n] ); |
Collapse file Copy file name to clipboard +13Lines changed: 13 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 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 Copy file name to clipboard +13Lines changed: 13 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +{ | | 2 | + "Longest Common Subsequence": "The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences)." , | | 3 | + "Complexity": { | | 4 | + "time": "O(mn)", | | 5 | + "space": "O(mn)" | | 6 | + }, | | 7 | + "References": [ | | 8 | + "<a href='https://en.wikipedia.org/wiki/Longest_common_subsequence_problem'>Wikipedia</a>" | | 9 | + ], | | 10 | + "files": { | | 11 | + "basic": "Longest common subsequence" | | 12 | + } | | 13 | +} |
|