forked from SiZapPaaiGwat/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsuffix-tree.js
More file actions
72 lines (63 loc) · 1.87 KB
/
Copy pathsuffix-tree.js
File metadata and controls
72 lines (63 loc) · 1.87 KB
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
(function (exports) {
'use strict';
function Node(val) {
this.value = val;
this.nodes = {};
}
function SuffixTree() {
this.root = new Node();
}
SuffixTree.prototype.addNode = (function () {
function maxPrefix(a, b) {
var res = [];
for (var i = 0; i < Math.min(a.length, b.length); i += 1) {
if (a[i] === b[i]) {
res.push(a[i]);
} else {
return '';
}
}
return res.join('');
}
function addNode(suffix, current) {
// Empty string already exists in the suffix tree
if (!suffix) {
return;
}
// The suffix is already inside the tree
if (current.value === suffix) {
return;
}
// Insert recursively
if (current.nodes[suffix[0]]) {
return addNode(suffix.substr(1, suffix.length),
current.nodes[suffix[0]]);
}
// Find the maximum prefix and split the current node if prefix exists
var prefix = maxPrefix(current.value, suffix);
if (prefix.length) {
var temp = current.value;
var suffixSuffix = suffix.substr(prefix.length, suffix.length);
var currentSuffix = temp.substr(prefix.length, temp.length);
current.value = prefix;
addNode(currentSuffix, current);
addNode(suffixSuffix, current);
// If prefix doesn't exists add new child node
} else {
current.nodes[suffix[0]] = new Node(suffix);
}
}
return function (suffix) {
addNode(suffix, this.root);
};
}());
// O(n^2) or even O(n^3) because of maxPrefix
SuffixTree.prototype.build = function (string) {
this.root.value = string;
for (var i = 1; i < string.length; i += 1) {
this.addNode(string.substr(i, string.length));
}
};
exports.Node = Node;
exports.SuffixTree = SuffixTree;
}(typeof exports === 'undefined' ? window : exports));