Skip to content

Instantly share code, notes, and snippets.

@LeeYeeze
Last active August 29, 2015 14:16
Show Gist options
  • Save LeeYeeze/3b7c8bc2c0679483e5f5 to your computer and use it in GitHub Desktop.
Save LeeYeeze/3b7c8bc2c0679483e5f5 to your computer and use it in GitHub Desktop.
Trie for suffix, construction in O(n) JavaScript
function SuffixTrieNode() {
this.children = {};
this.link = null;
}
SuffixTrieNode.prototype.addLink = function(c, v) {
this.children[c] = v;
};
function SuffixTrie(s) {
this.root = new SuffixTrieNode();
this.remainder = 0;
this.longest = this.root;
for (var i = 0; i < s.length; i++) {
this.insert(s.charAt(i));
}
}
SuffixTrie.prototype.search = function(s) {
var node = this.root;
for (var i = 0; i < s.length; i++) {
if (node.children.hasOwnProperty(s.charAt(i)))
node = node.children[s.charAt(i)];
else
return false;
}
return true;
};
SuffixTrie.prototype.searchSuffix = function(s) {
}
SuffixTrie.prototype.longestRepeat = function() {
}
SuffixTrie.prototype.insert = function(ch) {
var current = this.longest;
var previous = null;
//var ch = s.charAt(i);
while (current !== null && !current.children.hasOwnProperty(ch)) {
var node = new SuffixTrieNode();
current.addLink(ch, node);
if (previous !== null) {
previous.link = node;
}
previous = node;
current = current.link;
}
if (current === null) {
previous.link = this.root;
} else {
previous.link = current.children[ch];
}
this.longest = this.longest.children[ch];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment