Anonymous user
Eertree: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|Python}}: added place holder) |
(→{{header|zkl}}: added code) |
||
Line 121:
=={{header|zkl}}==
{{trans|Python}}
<lang zkl></lang>▼
<lang zkl>
fcn init(length){
var edges=Dictionary(), # edges (or forward links). (char:Node)
link=Void, # suffix link (backward links)
sz =length; # node length.
}
}
class Eertree{
fcn init(string=Void){
var nodes=List(),
# two initial root nodes
rto=Node(-1), # odd length root node, or node -1
rte=Node(0); # even length root node, or node 0
rto.link=rte.link=rto; # Initialize empty tree
var S =Data(Void,0), # accumulated input string, T=S[1..i], byte buffer
maxSufT=rte; # maximum suffix of tree T
if(string) string.pump(addChar); // go ahead and build the tree
}
fcn get_max_suffix_pal(startNode,a){
# We traverse the suffix-palindromes of T in the order of decreasing length.
# For each palindrome we read its length k and compare T[i-k] against a
# until we get an equality or arrive at the -1 node.
u,i,k := startNode, S.len(), u.sz;
while(u.id!=rto.id and S.charAt(i - k - 1)!=a){
_assert_(u.id!=u.link.id); # Prevent infinte loop
u,k = u.link,u.sz;
}
return(u);
}
fcn addChar(a){
# We need to find the maximum suffix-palindrome P of Ta
# Start by finding maximum suffix-palindrome Q of T.
# To do this, we traverse the suffix-palindromes of T
# in the order of decreasing length, starting with maxSuf(T)
Q:=get_max_suffix_pal(maxSufT,a);
# We check Q to see whether it has an outgoing edge labeled by a.
createANewNode:=(not Q.edges.holds(a));
if(createANewNode){
P:=Node(Q.sz + 2); nodes.append(P);
if(P.sz==1) P.link=rte; # if P = a, create the suffix link (P,0)
else # It remains to create the suffix link from P if |P|>1. Just
# continue traversing suffix-palindromes of T starting with the suffix
# link of Q.
P.link=get_max_suffix_pal(Q.link,a).edges[a];
Q.edges[a]=P; # create the edge (Q,P)
}
maxSufT=Q.edges[a]; # P becomes the new maxSufT
S.append(a); # Store accumulated input string
return(createANewNode); // in case anyone wants to know a is new edge
}
fcn get_sub_palindromes{
result:=List();
sub_palindromes(rto, T(rto),"", result); # Odd length words
sub_palindromes(rte, T(rte),"", result); # Even length words
result
}
fcn [private] sub_palindromes(nd, nodesToHere, charsToHere, result){
// nodesToHere needs to be read only
# Each node represents a palindrome, which can be reconstructed
# by the path from the root node to each non-root node.
# Traverse all edges, since they represent other palindromes
nd.edges.pump(Void,'wrap([(lnkName,nd2)]){
sub_palindromes(nd2, nodesToHere+nd2, charsToHere+lnkName, result);
});
# Reconstruct based on charsToHere characters.
if(nd.id!=rto.id and nd.id!=rte.id){ # Don't print for root nodes
if(nodesToHere[0].id==rte.id) # Even string
assembled:=charsToHere.reverse() + charsToHere;
else assembled:=charsToHere.reverse() + charsToHere[1,*]; # Odd string
result.append(assembled);
}
}
}</lang>
println("Processing string \"", st,"\"");
eertree:=Eertree(st);
println("Number of sub-palindromes: ", eertree.nodes.len());
println("Sub-palindromes: ", eertree.get_sub_palindromes());</lang>
{{out}}
<pre>
| |||