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 {
    construct new() {
        _edges = {}    // edges (or forward links)
        _link = null   // suffix link (backward links)
        _len = 0       // the length of the node
    }
 
    edges    { _edges }
    link     { _link }
    link=(l) { _link = l }
    len      { _len }
    len=(l)  { _len = l }
}
 
class Eertree {
    construct new(str) {
        _nodes = []
        _rto = Node.new()  // odd length root node, or node -1
        _rte = Node.new()  // even length root node, or node 0
        _s = "0"           // accumulated input string, T = S[1..i]
        _maxSufT = _rte    // maximum suffix of tree T
 
        // Initialize and build the tree
        _rte.link = _rto
        _rto.link = _rte
        _rto.len  = -1
        _rte.len  = 0
        for (ch in str) add_(ch)
    }
 
    nodes { _nodes }
 
    getMaxSuffixPal_(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.
        var u = startNode
        var i = _s.count
        var k = u.len
        while (u != _rto && _s[i - k - 1] != a) {
            if (u == u.link) Fiber.abort("Infinite loop detected")
            u = u.link
            k = u.len
        }
        return u
    }
 
    add_(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)
        var q = getMaxSuffixPal_(_maxSufT, a)
        // We check Q to see whether it has an outgoing edge labeled by a.
        var createANewNode = !q.edges.keys.contains(a)
 
        if (createANewNode) {
            // We create the node P of length Q + 2
            var p = Node.new()
            _nodes.add(p)
            p.len = q.len + 2
            if (p.len == 1) {
                // if P = a, create the suffix link (P, 0)
                p.link = _rte
            } else {
                // It remains to create the suffix link from P if |P|>1. Just
                // continue traversing suffix-palindromes of T starting with the
                // the suffix link of Q.
                p.link = getMaxSuffixPal_(q.link, a).edges[a]
            }
 
            // create the edge (Q, P)
            q.edges[a] = p
        }
 
        // P becomes the new maxSufT
        _maxSufT = q.edges[a]
 
        // Store accumulated input string
        _s = _s + a
 
        return createANewNode
    }
 
    getSubPalindromes() {
        // Traverse tree to find sub-palindromes
        var result = []
        // Odd length words
        getSubPalindromes_(_rto, [_rto], "", result)
        // Even length words
        getSubPalindromes_(_rte, [_rte], "", result)
        return result
    }
 
    getSubPalindromes_(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.keys) {
            var nd2 = nd.edges[lnkName]
            getSubPalindromes_(nd2, nodesToHere + [nd2], charsToHere + lnkName, result)
        }
 
        // Reconstruct based on charsToHere characters.
        if (nd != _rto && nd != _rte) { // Don't print for root nodes
            var assembled = charsToHere[-1..0] +
                ((nodesToHere[0] == _rte) ? charsToHere : charsToHere[1..-1])
            result.add(assembled)
        }
    }
}
 
var str = "eertree"
System.print("Processing string '%(str)'")
var eertree = Eertree.new(str)
System.print("Number of sub-palindromes: %(eertree.nodes.count)")
var result = eertree.getSubPalindromes()
System.print("Sub-palindromes: %(result)")