An eertree is a data structure designed for efficient processing of certain palindrome tasks, for instance counting the number of sub-palindromes in an input string.

The data structure has commonalities to both tries and suffix trees.
  See links below.



Task

Construct an eertree for the string "eertree", then output all sub-palindromes by traversing the tree.



See also

   Wikipedia entry:   trie.
   Wikipedia entry:   suffix tree 
   Cornell University Library, Computer Science, Data Structures and Algorithms ───► EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.


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);
      }
   }
}