Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0e23f0c

Browse files
authored
Merge pull requestmgechev#115 from krzysztof-grzybek/longest-common-subsequence
mgechev#111 Longest common subsequence
2 parentsb61a63b +57989d5 commit0e23f0c

4 files changed

+149
-14
lines changed
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
(function(exports){
2+
'use strict';
3+
4+
exports.longestCommonSubsequence=(function(){
5+
6+
/**
7+
* Find the lengths of longest common sub-sequences
8+
* of two strings and their substrings.
9+
*
10+
* Complexity: O(MN).
11+
*
12+
*@private
13+
*@param {String} first string
14+
*@param {String} second string
15+
*@return {Array} two dimensional array with LCS
16+
* lengths of input strings and their substrings.
17+
*
18+
*/
19+
functiongetLcsLengths(str1,str2){
20+
varresult=[];
21+
for(vari=-1;i<str1.length;i=i+1){
22+
result[i]=[];
23+
for(varj=-1;j<str2.length;j=j+1){
24+
if(i===-1||j===-1){
25+
result[i][j]=0;
26+
}elseif(str1[i]===str2[j]){
27+
result[i][j]=result[i-1][j-1]+1;
28+
}else{
29+
result[i][j]=Math.max(result[i-1][j],result[i][j-1]);
30+
}
31+
}
32+
}
33+
returnresult;
34+
}
35+
36+
/**
37+
* Find longest common sub-sequences of two strings.
38+
*
39+
* Complexity: O(M + N).
40+
*
41+
*@private
42+
*@param {String} first string
43+
*@param {String} second string
44+
*@return {Array} two dimensional array with LCS
45+
* lengths of input strings and their substrings
46+
* returned from 'getLcsLengths' function.
47+
*
48+
*/
49+
functiongetLcs(str1,str2,lcsLengthsMatrix){
50+
varexecute=function(i,j){
51+
if(!lcsLengthsMatrix[i][j]){
52+
return'';
53+
}elseif(str1[i]===str2[j]){
54+
returnexecute(i-1,j-1)+str1[i];
55+
}elseif(lcsLengthsMatrix[i][j-1]>lcsLengthsMatrix[i-1][j]){
56+
returnexecute(i,j-1);
57+
}else{
58+
returnexecute(i-1,j);
59+
}
60+
};
61+
returnexecute(str1.length-1,str2.length-1);
62+
}
63+
64+
/**
65+
* Algorithm from dynamic programming. It finds the longest
66+
* common sub-sequence of two strings. For example for strings 'abcd'
67+
* and 'axxcda' the longest common sub-sequence is 'acd'.
68+
*
69+
*@example
70+
* var subsequence = require('path-to-algorithms/src/searching/'+
71+
* 'longest-common-subsequence').longestCommonSubsequence;
72+
* console.log(subsequence('abcd', 'axxcda'); // 'acd'
73+
*
74+
*@public
75+
*@module searching/longest-common-subsequence
76+
*@param {String} first input string.
77+
*@param {String} second input string.
78+
*@return {Array} Longest common subsequence.
79+
*/
80+
returnfunction(str1,str2){
81+
varlcsLengthsMatrix=getLcsLengths(str1,str2);
82+
returngetLcs(str1,str2,lcsLengthsMatrix);
83+
};
84+
})();
85+
86+
})(typeofwindow==='undefined' ?module.exports :window);

‎src/searching/longest-subsequence.jsrenamed to‎src/searching/longest-increasing-subsequence.js

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
(function(exports){
22
'use strict';
33

4-
exports.longestSubsequence=(function(){
4+
exports.longestIncreasingSubsequence=(function(){
55

66
/**
77
* Find the index of the first largest element in array.
@@ -57,12 +57,12 @@
5757
}
5858

5959
/**
60-
* Finds the longest sub-sequence for given node.<br><br>
60+
* Finds the longestincreasingsub-sequence for given node.<br><br>
6161
* Complexity: O(N^N).
6262
*@private
6363
*@param {Object} dag Graph represented with list of neighbours.
6464
*@param {number} node The current node.
65-
*@return {object} The longest sub-sequence for given node.
65+
*@return {object} The longestincreasingsub-sequence for given node.
6666
*/
6767
functionfind(dag,node){
6868
node=node||0;
@@ -103,7 +103,7 @@
103103
*
104104
*@example
105105
* var subsequence = require('path-to-algorithms/src/searching/'+
106-
* 'longest-increasing-subsequence').longestSubsequence;
106+
* 'longest-increasing-subsequence').longestIncreasingSubsequence;
107107
* console.log(subsequence([1, 0, 4, 3, 5])); // 1, 4, 5
108108
*
109109
*@public
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
'use strict';
2+
3+
varlongestCommonSubsequence=
4+
require('../../src/searching/'+
5+
'longest-common-subsequence')
6+
.longestCommonSubsequence;
7+
8+
describe('longest common subsequence',function(){
9+
10+
it('should work with empty strings',function(){
11+
expect(longestCommonSubsequence('','')).toBe('');
12+
});
13+
14+
it('should work with first string empty',function(){
15+
expect(longestCommonSubsequence('','abcd')).toBe('');
16+
});
17+
18+
it('should work with second string empty',function(){
19+
expect(longestCommonSubsequence('abcd','')).toBe('');
20+
});
21+
22+
it('should work if there is no lcs',function(){
23+
expect(longestCommonSubsequence('qtwer','zvxcv')).toBe('');
24+
});
25+
26+
it('should work if lcs is whole first string',function(){
27+
expect(longestCommonSubsequence('abc','abcdefghi')).toBe('abc');
28+
});
29+
30+
it('should work if lcs is whole second string',function(){
31+
expect(longestCommonSubsequence('qwerty','rty')).toBe('rty');
32+
});
33+
34+
it('should work with repeated letter',function(){
35+
expect(longestCommonSubsequence('AAATC','GGTAGGC')).toBe('AC');
36+
});
37+
38+
it('should work with custom characters',function(){
39+
expect(longestCommonSubsequence(':-)','B-)')).toBe('-)');
40+
});
41+
42+
it('should work with long strings',function(){
43+
expect(longestCommonSubsequence('this is the first string','that is second')).toBe('tht is sn');
44+
});
45+
46+
it('should work with very long strings',function(){
47+
expect(longestCommonSubsequence('giiiiiiit1huuuuuu2bbb','zzxxcvasdfgmntplpliiggggu2b222')).toBe('giiu2b');
48+
});
49+
});

‎test/searching/longest-subsequence.spec.jsrenamed to‎test/searching/longest-increasing-subsequence.spec.js

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,36 @@
11
'use strict';
22

3-
varlongestSubsequence=
3+
varlongestIncreasingSubsequence=
44
require('../../src/searching/'+
5-
'longest-subsequence')
6-
.longestSubsequence;
5+
'longest-increasing-subsequence')
6+
.longestIncreasingSubsequence;
77

8-
describe('longest subsequence',function(){
8+
describe('longestincreasingsubsequence',function(){
99

1010
varsequence;
1111
beforeEach(function(){
1212
sequence=[5,2,8,6,3,6,9,7,11];
1313
});
1414

1515
it('should work with empty array',function(){
16-
expect(longestSubsequence([]).length).toBe(0);
16+
expect(longestIncreasingSubsequence([]).length).toBe(0);
1717
});
1818

1919
it('should return the only element in a single element array',function(){
2020
vararray=[1];
21-
expect(longestSubsequence(array)).toEqual([1]);
21+
expect(longestIncreasingSubsequence(array)).toEqual([1]);
2222
});
2323

2424
it('should give the right length',function(){
25-
expect(longestSubsequence(sequence).length).toBe(5);
25+
expect(longestIncreasingSubsequence(sequence).length).toBe(5);
2626
});
2727

2828
it('should work with empty arrays',function(){
29-
expect(longestSubsequence([]).length).toBe(0);
29+
expect(longestIncreasingSubsequence([]).length).toBe(0);
3030
});
3131

3232
it('should return the correct path',function(){
33-
expect(longestSubsequence(sequence).toString())
33+
expect(longestIncreasingSubsequence(sequence).toString())
3434
.toBe([2,3,6,9,11].toString());
3535
});
3636

@@ -39,7 +39,7 @@ describe('longest subsequence', function () {
3939
returnb-a;
4040
};
4141
varseq=[1,2,-1];
42-
varresult=longestSubsequence(seq,cmp);
42+
varresult=longestIncreasingSubsequence(seq,cmp);
4343
expect(result.length).toBe(2);
4444
expect(result).toEqual([1,-1]);
4545
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp