Anonymous user
Eertree: Difference between revisions
→{{header|JavaScript}}
m (→{{header|Wren}}: Changed to Wren S/H) |
imported>Patuitar |
||
Line 572:
{{out}}
<pre>[ee, r, t, rtr, ertre, eertree, e]</pre>
=={{header|JavaScript}}==
{{trans|Python}}
<syntaxhighlight lang="julia">
class Node {
constructor(len, suffix, id, level) {
this.edges = new Map(); // edges <Character, Node>
this.link = suffix; // Suffix link points to another node
this.length = len; // Length of the palindrome represented by this node
this.palindrome = "";
this.parent = null;
}
}
class Eertree {
constructor() {
this.imaginary = new Node(-1, null, this.count++, 1); // also called odd length root node
this.empty = new Node(0, this.imaginary, this.count++, 2); // also called even length root node
this.maxSuffixOfT = this.empty; // this is the current node we are on also the maximum Suffix of tree T
this.s = ""; // String processed by the Eertree
}
/**
* Add will only add at most 1 node to the tree.
* We get the max suffix palindrome with the same character before it
* so we can get cQc which will be the new palindrome, c otherwise
* If the node is already in the tree then we return 0 and create no new nodes
* @param {Character} c
* @returns int 1 if it created a new node an 0 otherwise
*/
add(c){
/**
* Traverse the suffix palindromes of T in the order of decreasing length
* Keep traversing until we get to imaginary node or until T[len - k] = a
* @param {Node} startNode
* @param {Character} a
* @returns {Node} u
*/
const getMaxSuffixPalindrome = (startNode, a) =>{
let u = startNode;
let n = this.s.length;
let k = u.length;
while(u !== this.imaginary && this.s[n - k - 1] !== a){
if(u === u.link){
throw new Error('Infinite Loop');
}
u = u.link;
k = u.length;
}
return u;
};
let Q = getMaxSuffixPalindrome(this.maxSuffixOfT, c);
let createNewNode = !(Q.edges.has(c));
if(createNewNode){
let P = new Node();
P.length = Q.length + 2;
// this is because Q is a palindrome and the suffix and prefix == c so cQc = P
//P.length == 1 if Q is the imaginary node
if(P.length === 1){
P.link = this.empty;
P.palindrome = c;
}
else{
/**
* Now we need to find the node to suffix link to
* Continue traversing suffix palindromes of T starting with the suffix
* we found earlier 's link
*/
P.link = getMaxSuffixPalindrome(Q.link, c).edges.get(c);
P.palindrome = c + Q.palindrome + c;
}
P.parent = Q;
Q.edges.set(c, P);
}
this.maxSuffixOfT = Q.edges.get(c);
this.s += c;
return createNewNode === true ? 1 : 0;
}
}
</syntaxhighlight> {{output}} <pre>
Results of processing string "eertree":
Number of sub-palindromes: 7
Sub-palindromes: ["e", "r", "eertree", "ertre", "rtr", "t", "ee"]
</pre>
=={{header|Julia}}==
| |||