Skip to content

Commit 1834f40

Browse files
mgechevmgechev
committed
Exports suffix tree
1 parent adb8c01 commit 1834f40

File tree

1 file changed

+88
-79
lines changed

1 file changed

+88
-79
lines changed

‎src/data-structures/suffix-tree.js

Lines changed: 88 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -1,96 +1,105 @@
11
// TODO
22
// 1) The algorithm is quite ineffective, better use
33
// Ukkomen's algorithm to build it in O(n) complexity.
4-
function Node(val) {
5-
this.value = val;
6-
this.nodes = {};
7-
}
4+
(function (exports) {
5+
'use strict';
86

9-
function SuffixTree() {
10-
this.root = new Node();
11-
}
7+
function Node(val) {
8+
this.value = val;
9+
this.nodes = {};
10+
}
1211

13-
SuffixTree.prototype.addNode = (function () {
12+
function SuffixTree() {
13+
this.root = new Node();
14+
}
1415

15-
function maxPrefix(a, b) {
16-
var res = [];
17-
for (var i = 0; i < Math.min(a.length, b.length); i += 1) {
18-
if (a[i] === b[i]) {
19-
res.push(a[i]);
20-
} else {
21-
return '';
16+
SuffixTree.prototype.addNode = (function () {
17+
18+
function maxPrefix(a, b) {
19+
var res = [];
20+
for (var i = 0; i < Math.min(a.length, b.length); i += 1) {
21+
if (a[i] === b[i]) {
22+
res.push(a[i]);
23+
} else {
24+
return '';
25+
}
2226
}
27+
return res.join('');
2328
}
24-
return res.join('');
25-
}
2629

27-
function addNode(suffix, current) {
28-
// Empty string already exists in the suffix tree
29-
if (!suffix) {
30-
return;
31-
}
32-
// The suffix is already inside the tree
33-
if (current.value === suffix) {
34-
return;
35-
}
36-
// Insert recursively
37-
if (current.nodes[suffix[0]]) {
38-
return addNode(suffix.substr(1, suffix.length), current.nodes[suffix[0]]);
39-
}
40-
// Find the maximum prefix and split the current node if prefix exists
41-
var prefix = maxPrefix(current.value, suffix);
42-
if (prefix.length) {
43-
var temp = current.value,
44-
suffixSuffix = suffix.substr(prefix.length, suffix.length),
45-
currentSuffix = temp.substr(prefix.length, temp.length);
46-
current.value = prefix;
47-
addNode(currentSuffix, current);
48-
addNode(suffixSuffix, current);
49-
// If prefix doesn't exists add new child node
50-
} else {
51-
current.nodes[suffix[0]] = new Node(suffix);
30+
function addNode(suffix, current) {
31+
// Empty string already exists in the suffix tree
32+
if (!suffix) {
33+
return;
34+
}
35+
// The suffix is already inside the tree
36+
if (current.value === suffix) {
37+
return;
38+
}
39+
// Insert recursively
40+
if (current.nodes[suffix[0]]) {
41+
return addNode(suffix.substr(1, suffix.length),
42+
current.nodes[suffix[0]]);
43+
}
44+
// Find the maximum prefix and split the current node if prefix exists
45+
var prefix = maxPrefix(current.value, suffix);
46+
if (prefix.length) {
47+
var temp = current.value,
48+
suffixSuffix = suffix.substr(prefix.length, suffix.length),
49+
currentSuffix = temp.substr(prefix.length, temp.length);
50+
current.value = prefix;
51+
addNode(currentSuffix, current);
52+
addNode(suffixSuffix, current);
53+
// If prefix doesn't exists add new child node
54+
} else {
55+
current.nodes[suffix[0]] = new Node(suffix);
56+
}
5257
}
53-
}
5458

55-
return function (suffix) {
56-
addNode(suffix, this.root);
59+
return function (suffix) {
60+
addNode(suffix, this.root);
61+
};
62+
}());
63+
64+
// O(n^2) or even O(n^3) because of maxPrefix
65+
SuffixTree.prototype.build = function (string) {
66+
this.root.value = string;
67+
for (var i = 1; i < string.length; i += 1) {
68+
this.addNode(string.substr(i, string.length));
69+
}
5770
};
58-
}());
5971

60-
// O(n^2) or even O(n^3) because of maxPrefix
61-
SuffixTree.prototype.build = function (string) {
62-
this.root.value = string;
63-
for (var i = 1; i < string.length; i += 1) {
64-
this.addNode(string.substr(i, string.length));
65-
}
66-
};
6772

73+
// function isSubstr(tree, str) {
74+
// if (!tree) {
75+
// return false;
76+
// }
77+
// if (tree.nodes[str[0]]) {
78+
// return isSubstr(tree, str.substr(1, str.length));
79+
// }
80+
// var match = '';
81+
// for (var i = 0; i < Math.min(tree.value.length, str.length); i += 1) {
82+
// if (tree.value[i] === str[i]) {
83+
// match += str[i];
84+
// } else {
85+
// break;
86+
// }
87+
// }
88+
// if (match.length === str.length) {
89+
// return true;
90+
// }
91+
// return false;
92+
// }
6893

69-
function isSubstr(tree, str) {
70-
if (!tree) {
71-
return false;
72-
}
73-
if (tree.nodes[str[0]]) {
74-
return isSubstr(tree, str.substr(1, str.length));
75-
}
76-
var match = '';
77-
for (var i = 0; i < Math.min(tree.value.length, str.length); i += 1) {
78-
if (tree.value[i] === str[i]) {
79-
match += str[i];
80-
} else {
81-
break;
82-
}
83-
}
84-
if (match.length === str.length) {
85-
return true;
86-
}
87-
return false;
88-
}
94+
// var suffix = new SuffixTree();
95+
// suffix.build('banana');
96+
// console.log(suffix);
97+
//
98+
// var st = new SuffixTree();
99+
// st.build('Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.');
100+
// console.log(JSON.stringify(st));
89101

90-
// var suffix = new SuffixTree();
91-
// suffix.build('banana');
92-
// console.log(suffix);
102+
exports.Node = Node;
103+
exports.SuffixTree = SuffixTree;
93104

94-
var st = new SuffixTree();
95-
st.build('Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.');
96-
console.log(JSON.stringify(st));
105+
}(typeof exports === 'undefined' ? window : exports));

0 commit comments

Comments
 (0)