Eertree

Eertree is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 suffix tries and suffix trees.

Task

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

Python

<lang python>#!/bin/python from __future__ import print_function

class Node(object): def __init__(self): self.edges = {} # edges (or forward links) self.link = None # suffix link (backward links) self.len = 0 # the length of the node

class Eertree(object): def __init__(self): self.nodes = [] # two initial root nodes self.rto = Node() #odd length root node, or node -1 self.rte = Node() #even length root node, or node 0

# Initialize empty tree self.rto.link = self.rte.link = self.rto; self.rto.len = -1 self.rte.len = 0 self.S = [0] # accumulated input string, T=S[1..i] self.maxSufT = self.rte # maximum suffix of tree T

def get_max_suffix_pal(self, 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 = startNode i = len(self.S) k = u.len while id(u) != id(self.rto) and self.S[i - k - 1] != a: assert id(u) != id(u.link) #Prevent infinte loop u = u.link k = u.len

return u

def add(self, 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 = self.get_max_suffix_pal(self.maxSufT, a)

# We check Q to see whether it has an outgoing edge labeled by a. createANewNode = not a in Q.edges

if createANewNode: # We create the node P of length Q+2 P = Node() self.nodes.append(P) P.len = Q.len + 2 if P.len == 1: # if P = a, create the suffix link (P,0) P.link = self.rte 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 = self.get_max_suffix_pal(Q.link, a).edges[a]

# create the edge (Q,P) Q.edges[a] = P

#P becomes the new maxSufT self.maxSufT = Q.edges[a]

#Store accumulated input string self.S.append(a)

return createANewNode

def get_sub_palindromes(self, nd, nodesToHere, charsToHere, result): #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 for lnkName in nd.edges: nd2 = nd.edges[lnkName] #The lnkName is the character used for this edge self.get_sub_palindromes(nd2, nodesToHere+[nd2], charsToHere+[lnkName], result)

#Reconstruct based on charsToHere characters. if id(nd) != id(self.rto) and id(nd) != id(self.rte): #Don't print for root nodes tmp = "".join(charsToHere) if id(nodesToHere[0]) == id(self.rte): #Even string assembled = tmp[::-1] + tmp else: #Odd string assembled = tmp[::-1] + tmp[1:] result.append(assembled)

if __name__=="__main__": st = "eertree" print ("Processing string", st) eertree = Eertree() for ch in st: eertree.add(ch)

print ("Number of sub-palindromes:", len(eertree.nodes))

#Traverse tree to find sub-palindromes result = [] eertree.get_sub_palindromes(eertree.rto, [eertree.rto], [], result) #Odd length words eertree.get_sub_palindromes(eertree.rte, [eertree.rte], [], result) #Even length words print ("Sub-palindromes:", result)</lang>

Output:

Processing string eertree
Number of sub-palindromes: 7
Sub-palindromes: ['r', 'e', 'eertree', 'ertre', 'rtr', 't', 'ee']

Racket

Translation of: Python

zkl

Translation of: Python

<lang zkl>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);

     }
  }

}</lang> <lang zkl>st:="eertree"; println("Processing string \"", st,"\""); eertree:=Eertree(st); println("Number of sub-palindromes: ", eertree.nodes.len()); println("Sub-palindromes: ", eertree.get_sub_palindromes());</lang>

Output:

Processing string "eertree"
Number of sub-palindromes: 7
Sub-palindromes: L("e","r","eertree","ertre","rtr","t","ee")