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.


/*REXX program creates a list of (unique) sub─palindromes that exist in an input string.*/
parse arg x .                                    /*obtain optional input string from CL.*/
if x=='' | x==","  then x= 'eertree'             /*Not specified?  Then use the default.*/
L= length(x)                                     /*the length (in chars) of input string*/
@.= .                                            /*@ tree indicates uniqueness of pals. */
$=                                               /*list of unsorted & unique palindromes*/
   do     j=1  for L                             /*start at the left side of the string.*/
       do k=1  for L                             /*traverse from left to right of string*/
       parse var  x   =(j)  y   +(k)             /*extract a substring from the string. */
       if reverse(y)\==y | @.y\==.  then iterate /*Partial string a palindrome?  Skip it*/
       @.y= y                                    /*indicate a sub─palindrome was found. */
       $= $' '  y                                /*append the sub─palindrome to the list*/
       end   /*k*/                               /* [↑]  an extra blank is inserted.    */
   end       /*j*/
 
say '──────── The input string that is being used: '     space(x)
say '──────── The number of sub─palindromes found: '     words($)
say '──────── The  list  of sub─palindromes found: '     strip($)
                                                 /*stick a fork in it,  we're all done. */