AlgorithmVisualizer/algorithm/dp/longest_common_subsequence/basic/code.js at master · resida/AlgorithmVisualizer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
var i,j;

// Build the memo table in bottom up fashion
 for( i = 0; i <= m; i++ ) {
 	for( j = 0; j <= n; j++ ) {
 		if ( i === 0 || j === 0 ) {
 			A[i][j] = 0;
 		} 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] = A[i-1][j];
 			} else {
 				A[i][j] = 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 );
 	}
 }

var finalString = '';
i=m;
j=n;
while( i>=1 && j>=1 ) {

	tracer3._select ( i, j )._wait ();
	if( string1[i-1] == string2[j-1] ) {
		tracer1._select ( i-1 )._wait ();
 		tracer2._select ( j-1 )._wait ();

		finalString = string1[i-1] + finalString;
		i--;
		j--;
	} else if( A[i-1][j] > A[i][j-1] ) {
		i--;
	} else {
		j--;
	}
}

logger._print ( 'Longest Common Subsequence Length is ' + A[m][n] );
logger._print ( 'Longest Common Subsequence is ' + finalString );