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.


 
If Version<9.5 Then exit
If Version=9.5 And Revision<2 Then Exit
Class Node {
      inventory myedges
      length, suffix=0
      Function edges(s$) {
            =-1 : if exist(.myedges, s$) then =eval(.myedges)
      }
      Module edges_append (a$, where) {
            Append .myedges, a$:=where
      }
Class:
      Module Node(.length) {
            Read ? .suffix, .myedges
      }     
}
function eertree(s$) {
      Const evenRoot=0, oddRoot=1
      Inventory Tree= oddRoot:=Node(-1,1),evenRoot:=Node(0,1)
      k=0
      suffix=oddRoot
      for i=0 to len(s$)-1 {
            c$=mid$(s$,i+1,1)
            n=suffix
            Do {
                 k=tree(n).length
                 b=i-k-1
                  if b>=0 then if mid$(s$,b+1,1)=c$ Then exit
                  n =tree(n).suffix  
            } Always
            e=tree(n).edges(c$)
            if e>=0 then suffix=e :continue
            suffix=len(Tree)
 
            Append Tree, len(Tree):=Node(k+2)
            Tree(n).edges_append c$, suffix
            If tree(suffix).length=1 then tree(suffix).suffix=0 : continue
            Do {
                  n=tree(n).suffix
                  b=i-tree(n).length-1
                  if b>0 Then If  mid$(s$, b+1,1)=c$ then exit
            } Always
            e=tree(n).edges(c$)
            if e>=0 then tree(suffix).suffix=e
 
      } 
      =tree
}
children=lambda (s, tree,  n, root$="")->{
            L=Len(tree(n).myEdges)
            if L=0 then =s : exit
            L--
            For i=0 to L {
                  c=tree(n).myEdges
                  c$=Eval$(c, i)  ' read keys at position i
                  nxt=c(i!)   '  read value using position 
                  p$ = if$(n=1 -> c$, c$+root$+c$)
                  append s, (p$,)
                  \\ better use lambda() and not children()
                  \\ for recursion when we copy this lambda to other identifier.
                  s = lambda(s, tree, nxt, p$)
            }
         = s
      }
aString=Lambda ->{
          Push Quote$(Letter$)
}
aLine=Lambda ->{
      Shift 2  ' swap two top stack items
      if stackitem$()="" then  { Drop}  Else Push letter$+", "+Letter$
}
Palindromes$=Lambda$ children, aString, aLine (Tree)-> {
            ="("+children(children((,), Tree, 0), Tree, 1)#Map(aString)#Fold$(aline,"")+")"
 }
 
Print Palindromes$(eertree("eertree"))
 