76 lines
3 KiB
Text
76 lines
3 KiB
Text
class Node{
|
|
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);
|
|
}
|
|
}
|
|
}
|