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.


with javascript_semantics
enum LEN,SUFF,CHARS,NEXT
 
function node(integer len, suffix=1, string chars="", sequence next={})
    return {len,suffix,chars,next} -- must match above enum!
end function 
 
function eertree(string s)
sequence tree = {node(-1),  -- odd lengths
                 node(0)}   -- even lengths
integer suff = 2    -- max suffix palindrome
 
    for i=1 to length(s) do
        integer cur = suff, curlen, ch = s[i], k
        while (true) do
            curlen = tree[cur][LEN]
            k = i-1-curlen
            if k>=1 and s[k]==ch then
                exit
            end if
            cur = tree[cur][SUFF]
        end while
        k = find(ch,tree[cur][CHARS])
        if k then
            suff = tree[cur][NEXT][k]
        else
            tree = append(tree,node(curlen+2))
            suff = length(tree)
            tree[cur][CHARS] &= ch
            tree[cur][NEXT] = deep_copy(tree[cur][NEXT])&suff
 
            if tree[suff][LEN]==1 then
                tree[suff][SUFF] = 2
            else
                while (true) do
                    cur = tree[cur][SUFF]
                    curlen = tree[cur][LEN]
                    k = i-1-curlen
                    if k>=0 and s[k]==ch then
                        k = find(ch,tree[cur][CHARS])
                        if k then
                            tree[suff][SUFF] = tree[cur][NEXT][k]
                        end if
                        exit
                    end if
                end while
            end if
        end if
    end for
    return tree
end function
 
function children(sequence s, tree, integer n, string root="")
    for i=1 to length(tree[n][CHARS]) do
        integer c = tree[n][CHARS][i],
                nxt = tree[n][NEXT][i]
        string p = iff(n=1 ? c&""
                           : c&root&c)
        s = append(s, p)
        s = children(s, tree, nxt, p)
    end for
    return s
end function
 
procedure main()
    sequence tree = eertree("eertree")
    puts(1,"tree:\n")
    for i=1 to length(tree) do
        sequence ti = deep_copy(tree[i])
        ti[NEXT] = sprint(ti[NEXT])
        ti = i&ti
        printf(1,"[%d]: len:%2d  suffix:%d  chars:%-5s next:%s\n",ti)
    end for
    puts(1,"\n")
 
    -- odd then even lengths:
    ?children(children({},tree,1), tree, 2)
end procedure
main()
