Eertree

Eertree
You are encouraged to solve this task according to the task description, using any language you may know.

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.
• EERTREE: An efficient data structure for processing palindromes in strings[1]

11l

Translation of: D

T Node
   Int length
   Int suffix
   [Char = Int] edges

   F (length, suffix = 0)
      .length = length
      .suffix = suffix

-V oddRoot = 1

F eertree(s)
   V tree = [Node(0, :oddRoot), Node(-1, :oddRoot)]
   V suffix = :oddRoot
   L(c) s
      V i = L.index
      V n = suffix
      Int k
      L
         k = tree[n].length
         V b = i - k - 1
         I b >= 0 & s[b] == c
            L.break
         n = tree[n].suffix

      V? edge = tree[n].edges.find(c)
      I edge != N
         suffix = edge
         L.continue

      suffix = tree.len
      tree [+]= Node(k + 2)
      tree[n].edges[c] = suffix
      I tree[suffix].length == 1
         tree[suffix].suffix = 0
         L.continue

      L
         n = tree[n].suffix
         V b = i - tree[n].length - 1
         I b >= 0 & s[b] == c
            L.break

      tree[suffix].suffix = tree[n].edges[c]

   R tree

F subPalindromes(tree)
   [String] s

   F children(Int n, String =p) -> Void
      L(c, n) @tree[n].edges
         p = c‘’p‘’c
         @s [+]= p
         @children(n, p)

   children(0, ‘’)
   L(c, n) tree[1].edges
      s [+]= c
      children(n, c)

   R s

V tree = eertree(‘eertree’)
print(subPalindromes(tree))

Output:

[ee, e, r, t, rtr, ertre, eertree]

C#

Translation of: Java

using System;
using System.Collections.Generic;

namespace Eertree {
    class Node {
        public Node(int length) {
            this.Length = length;
            // empty or
            this.Edges = new Dictionary<char, int>();
        }

        public Node(int length, Dictionary<char, int> edges, int suffix) {
            this.Length = length;
            this.Edges = edges;
            this.Suffix = suffix;
        }

        public int Length { get; set; }
        public Dictionary<char, int> Edges { get; set; }
        public int Suffix { get; set; }
    }

    class Program {
        const int EVEN_ROOT = 0;
        const int ODD_ROOT = 1;

        static List<Node> Eertree(string s) {
            List<Node> tree = new List<Node> {
                //new Node(0, null, ODD_ROOT), or
                new Node(0, new Dictionary<char, int>(), ODD_ROOT),
                //new Node(-1, null, ODD_ROOT) or
                new Node(-1, new Dictionary<char, int>(), ODD_ROOT)
            };
            int suffix = ODD_ROOT;
            int n, k;
            for (int i = 0; i < s.Length; i++) {
                char c = s[i];
                for (n = suffix; ; n = tree[n].Suffix) {
                    k = tree[n].Length;
                    int b = i - k - 1;
                    if (b >= 0 && s[b] == c) {
                        break;
                    }
                }
                if (tree[n].Edges.ContainsKey(c)) {
                    suffix = tree[n].Edges[c];
                    continue;
                }
                suffix = tree.Count;
                tree.Add(new Node(k + 2));
                tree[n].Edges[c] = suffix;
                if (tree[suffix].Length == 1) {
                    tree[suffix].Suffix = 0;
                    continue;
                }
                while (true) {
                    n = tree[n].Suffix;
                    int b = i - tree[n].Length - 1;
                    if (b >= 0 && s[b] == c) {
                        break;
                    }
                }
                tree[suffix].Suffix = tree[n].Edges[c];
            }
            return tree;
        }

        static List<string> SubPalindromes(List<Node> tree) {
            List<string> s = new List<string>();
            SubPalindromes_children(0, "", tree, s);
            foreach (var c in tree[1].Edges.Keys) {
                int m = tree[1].Edges[c];
                string ct = c.ToString();
                s.Add(ct);
                SubPalindromes_children(m, ct, tree, s);
            }
            return s;
        }

        static void SubPalindromes_children(int n, string p, List<Node> tree, List<string> s) {
            foreach (var c in tree[n].Edges.Keys) {
                int m = tree[n].Edges[c];
                string p1 = c + p + c;
                s.Add(p1);
                SubPalindromes_children(m, p1, tree, s);
            }
        }

        static void Main(string[] args) {
            List<Node> tree = Eertree("eertree");
            List<string> result = SubPalindromes(tree);
            string listStr = string.Join(", ", result);
            Console.WriteLine("[{0}]", listStr);
        }
    }
}

Output:

[ee, e, r, t, rtr, ertre, eertree]

C++

Translation of: D

#include <iostream>
#include <functional>
#include <map>
#include <vector>

struct Node {
    int length;
    std::map<char, int> edges;
    int suffix;

    Node(int l) : length(l), suffix(0) {
        /* empty */
    }

    Node(int l, const std::map<char, int>& m, int s) : length(l), edges(m), suffix(s) {
        /* empty */
    }
};

constexpr int evenRoot = 0;
constexpr int oddRoot = 1;

std::vector<Node> eertree(const std::string& s) {
    std::vector<Node> tree = {
        Node(0, {}, oddRoot),
        Node(-1, {}, oddRoot)
    };
    int suffix = oddRoot;
    int n, k;

    for (size_t i = 0; i < s.length(); ++i) {
        char c = s[i];
        for (n = suffix; ; n = tree[n].suffix) {
            k = tree[n].length;
            int b = i - k - 1;
            if (b >= 0 && s[b] == c) {
                break;
            }
        }

        auto it = tree[n].edges.find(c);
        auto end = tree[n].edges.end();
        if (it != end) {
            suffix = it->second;
            continue;
        }
        suffix = tree.size();
        tree.push_back(Node(k + 2));
        tree[n].edges[c] = suffix;
        if (tree[suffix].length == 1) {
            tree[suffix].suffix = 0;
            continue;
        }
        while (true) {
            n = tree[n].suffix;
            int b = i - tree[n].length - 1;
            if (b >= 0 && s[b] == c) {
                break;
            }
        }
        tree[suffix].suffix = tree[n].edges[c];
    }

    return tree;
}

std::vector<std::string> subPalindromes(const std::vector<Node>& tree) {
    std::vector<std::string> s;

    std::function<void(int, std::string)> children;
    children = [&children, &tree, &s](int n, std::string p) {
        auto it = tree[n].edges.cbegin();
        auto end = tree[n].edges.cend();
        for (; it != end; it = std::next(it)) {
            auto c = it->first;
            auto m = it->second;

            std::string pl = c + p + c;
            s.push_back(pl);
            children(m, pl);
        }
    };
    children(0, "");

    auto it = tree[1].edges.cbegin();
    auto end = tree[1].edges.cend();
    for (; it != end; it = std::next(it)) {
        auto c = it->first;
        auto n = it->second;

        std::string ct(1, c);
        s.push_back(ct);

        children(n, ct);
    }

    return s;
}

int main() {
    using namespace std;

    auto tree = eertree("eertree");
    auto pal = subPalindromes(tree);

    auto it = pal.cbegin();
    auto end = pal.cend();

    cout << "[";
    if (it != end) {
        cout << it->c_str();
        it++;
    }
    while (it != end) {
        cout << ", " << it->c_str();
        it++;
    }
    cout << "]" << endl;

    return 0;
}

Output:

[ee, e, r, t, rtr, ertre, eertree]

D

Translation of: Go

import std.array;
import std.stdio;

void main() {
    auto tree = eertree("eertree");
    writeln(subPalindromes(tree));
}

struct Node {
    int length;
    int[char] edges;
    int suffix;
}

const evenRoot = 0;
const oddRoot = 1;

Node[] eertree(string s) {
    Node[] tree = [
        Node(0, null, oddRoot),
        Node(-1, null, oddRoot),
    ];
    int suffix = oddRoot;
    int n, k;
    foreach (i, c; s) {
        for (n=suffix; ; n=tree[n].suffix) {
            k = tree[n].length;
            int b = i-k-1;
            if (b>=0 && s[b]==c) {
                break;
            }
        }
        if (c in tree[n].edges) {
            suffix = tree[n].edges[c];
            continue;
        }
        suffix = tree.length;
        tree ~= Node(k+2);
        tree[n].edges[c] = suffix;
        if (tree[suffix].length == 1) {
            tree[suffix].suffix = 0;
            continue;
        }
        while (true) {
            n = tree[n].suffix;
            int b = i-tree[n].length-1;
            if (b>=0 && s[b]==c) {
                break;
            }
        }
        tree[suffix].suffix = tree[n].edges[c];
    }
    return tree;
}

auto subPalindromes(Node[] tree) {
    auto s = appender!(string[]);
    void children(int n, string p) {
        foreach (c, n; tree[n].edges) {
            p = c ~ p ~ c;
            s ~= p;
            children(n, p);
        }
    }
    children(0, "");
    foreach (c, n; tree[1].edges) {
        string ct = [c].idup;
        s ~= ct;
        children(n, ct);
    }
    return s.data;
}

Output:

["ee", "e", "r", "t", "rtr", "ertre", "eertree"]

FreeBASIC

Translation of: Ring

Dim As String cadena = "eertree"
Dim As Integer n, m, p, cnt = 0
Dim As String strpal, strrev
Dim As String pal(1 To Len(cadena)^2)

For n = 1 To Len(cadena)
    For m = n To Len(cadena)
        strpal = Mid(cadena, n, m-n+1)
        strrev = ""
        For p = Len(strpal) To 1 Step -1
            strrev &= Mid(strpal, p, 1)
        Next p
        If strpal = strrev Then
            cnt += 1
            pal(cnt) = strpal
        End If
    Next m
Next n

For n = 1 To cnt-1
    For m = n+1 To cnt
        If pal(n) > pal(m) Then
            Swap pal(n), pal(m)
        End If
    Next m
Next n

For n = cnt To 2 Step -1
    If pal(n) = pal(n-1) Then
        For m = n To cnt-1
            pal(m) = pal(m+1)
        Next m
        cnt -= 1
    End If
Next n

For n = 1 To cnt
    Print pal(n)
Next n

Sleep

Output:

Same as Ring entry.

Go

package main

import "fmt"

func main() {
    tree := eertree([]byte("eertree"))
    fmt.Println(subPalindromes(tree))
}

type edges map[byte]int

type node struct {
    length int
    edges
    suffix int
}

const evenRoot = 0
const oddRoot = 1

func eertree(s []byte) []node {
    tree := []node{
        evenRoot: {length: 0, suffix: oddRoot, edges: edges{}},
        oddRoot:  {length: -1, suffix: oddRoot, edges: edges{}},
    }
    suffix := oddRoot
    var n, k int
    for i, c := range s {
        for n = suffix; ; n = tree[n].suffix {
            k = tree[n].length
            if b := i - k - 1; b >= 0 && s[b] == c {
                break
            }
        }
        if e, ok := tree[n].edges[c]; ok {
            suffix = e
            continue
        }
        suffix = len(tree)
        tree = append(tree, node{length: k + 2, edges: edges{}})
        tree[n].edges[c] = suffix
        if tree[suffix].length == 1 {
            tree[suffix].suffix = 0
            continue
        }
        for {
            n = tree[n].suffix
            if b := i - tree[n].length - 1; b >= 0 && s[b] == c {
                break
            }
        }
        tree[suffix].suffix = tree[n].edges[c]
    }
    return tree
}

func subPalindromes(tree []node) (s []string) {
    var children func(int, string)
    children = func(n int, p string) {
        for c, n := range tree[n].edges {
            c := string(c)
            p := c + p + c
            s = append(s, p)
            children(n, p)
        }
    }
    children(0, "")
    for c, n := range tree[1].edges {
        c := string(c)
        s = append(s, c)
        children(n, c)
    }
    return
}

Output:

[ee e r t rtr ertre eertree]

Java

Translation of: D

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Eertree {
    public static void main(String[] args) {
        List<Node> tree = eertree("eertree");
        List<String> result = subPalindromes(tree);
        System.out.println(result);
    }

    private static class Node {
        int length;
        Map<Character, Integer> edges = new HashMap<>();
        int suffix;

        public Node(int length) {
            this.length = length;
        }

        public Node(int length, Map<Character, Integer> edges, int suffix) {
            this.length = length;
            this.edges = edges != null ? edges : new HashMap<>();
            this.suffix = suffix;
        }
    }

    private static final int EVEN_ROOT = 0;
    private static final int ODD_ROOT = 1;

    private static List<Node> eertree(String s) {
        List<Node> tree = new ArrayList<>();
        tree.add(new Node(0, null, ODD_ROOT));
        tree.add(new Node(-1, null, ODD_ROOT));
        int suffix = ODD_ROOT;
        int n, k;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            for (n = suffix; ; n = tree.get(n).suffix) {
                k = tree.get(n).length;
                int b = i - k - 1;
                if (b >= 0 && s.charAt(b) == c) {
                    break;
                }
            }
            if (tree.get(n).edges.containsKey(c)) {
                suffix = tree.get(n).edges.get(c);
                continue;
            }
            suffix = tree.size();
            tree.add(new Node(k + 2));
            tree.get(n).edges.put(c, suffix);
            if (tree.get(suffix).length == 1) {
                tree.get(suffix).suffix = 0;
                continue;
            }
            while (true) {
                n = tree.get(n).suffix;
                int b = i - tree.get(n).length - 1;
                if (b >= 0 && s.charAt(b) == c) {
                    break;
                }
            }
            tree.get(suffix).suffix = tree.get(n).edges.get(c);
        }
        return tree;
    }

    private static List<String> subPalindromes(List<Node> tree) {
        List<String> s = new ArrayList<>();
        subPalindromes_children(0, "", tree, s);
        for (Map.Entry<Character, Integer> cm : tree.get(1).edges.entrySet()) {
            String ct = String.valueOf(cm.getKey());
            s.add(ct);
            subPalindromes_children(cm.getValue(), ct, tree, s);
        }
        return s;
    }

    // nested methods are a pain, even if lambdas make that possible for Java
    private static void subPalindromes_children(final int n, final String p, final List<Node> tree, List<String> s) {
        for (Map.Entry<Character, Integer> cm : tree.get(n).edges.entrySet()) {
            Character c = cm.getKey();
            Integer m = cm.getValue();
            String pl = c + p + c;
            s.add(pl);
            subPalindromes_children(m, pl, tree, s);
        }
    }
}

Output:

[ee, r, t, rtr, ertre, eertree, e]

JavaScript

Translation of: Python

class Node {
    constructor(len, suffix, id, level) {
        this.edges = new Map(); // edges <Character, Node>
        this.link = suffix; // Suffix link points to another node
        this.length = len; // Length of the palindrome represented by this node
        this.palindrome = "";
        this.parent = null;
    }
}

class Eertree {
    constructor() {
        this.imaginary = new Node(-1, null, this.count++, 1); // also called odd length root node
        this.empty = new Node(0, this.imaginary, this.count++, 2); // also called even length root node
        this.maxSuffixOfT = this.empty; // this is the current node we are on also the maximum Suffix of tree T
        this.s = ""; // String processed by the Eertree
    }


    /**
     * Add will only add at most 1 node to the tree. 
     * We get the max suffix palindrome with the same character before it
     * so we can get cQc which will be the new palindrome, c otherwise
     * If the node is already in the tree then we return 0 and create no new nodes
     * @param {Character} c 
     * @returns int 1 if it created a new node an 0 otherwise
     */
    add(c){
        /**
         * Traverse the suffix palindromes of T in the order of decreasing length
         * Keep traversing until we get to imaginary node or until T[len - k] = a
         * @param {Node} startNode 
         * @param {Character} a
         * @returns {Node} u
         */
        const getMaxSuffixPalindrome = (startNode, a) =>{
            let u = startNode;
            let n = this.s.length;
            let k = u.length;
            while(u !== this.imaginary && this.s[n - k - 1] !== a){
                if(u === u.link){
                    throw new Error('Infinite Loop');
                }
                u = u.link;
                k = u.length;
            }
            return u;
        };


        let Q = getMaxSuffixPalindrome(this.maxSuffixOfT, c);
        let createNewNode = !(Q.edges.has(c));
        if(createNewNode){
            let P = new Node();
            P.length = Q.length + 2; 
            // this is because Q is a palindrome and the suffix and prefix == c so cQc = P
            //P.length == 1 if Q is the imaginary node
            if(P.length === 1){
                P.link = this.empty;
                P.palindrome = c;
            }
            else{
                /**
                 * Now we need to find the node to suffix link to
                 * Continue traversing suffix palindromes of T starting with the suffix
                 * we found earlier 's link
                 */
                P.link = getMaxSuffixPalindrome(Q.link, c).edges.get(c);
                P.palindrome = c + Q.palindrome + c;
            }
            P.parent = Q;
            Q.edges.set(c, P);
        }

        this.maxSuffixOfT = Q.edges.get(c);
        this.s += c;
        
        return createNewNode === true ? 1 : 0;
    }

    traverse(){
        let subpalindromes = [];

        const dfs = (node) => {
            if(node !== this.imaginary && node !== this.empty){
                subpalindromes.push(node.palindrome);
            }

            for(let [_, childNode] of node.edges){
                dfs(childNode);
            }
        }

        dfs(this.imaginary);
        dfs(this.empty);
        return subpalindromes;
    }
}

var getSubpalindromes = function(s) {
    let eertree = new Eertree();
    for(let c of s){
        eertree.add(c);
    }
    return eertree.traverse();
}

console.log(getSubpalindromes('eertree'));

Output:

Results of processing string "eertree":
Number of sub-palindromes: 7
Sub-palindromes: ["e", "r", "t", "rtr", "ertre", "eertree", "ee"]

Julia

Translation of: Python

mutable struct Node
    edges::Dict{Char, Node}
    link::Union{Node, Missing}
    sz::Int
    Node() = new(Dict(), missing, 0)
end

sizednode(x) = (n = Node(); n.sz = x; n)

function eertree(str)
    nodes = Vector{Node}()
    oddroot = sizednode(-1)
    evenroot = sizednode(0)
    oddroot.link = evenroot
    evenroot.link = oddroot
    S = "0"
    maxsuffix = evenroot

    function maxsuffixpal(startnode,a::Char)
        # Traverse the suffix-palindromes of tree looking for equality with a
        u = startnode
        i = length(S)
        k = u.sz
        while u !== oddroot && S[i - k] != a
            if u === u.link
                throw("circular reference above oddroot")
            end
            u = u.link
            k = u.sz
        end
        u
    end

    function addchar(a::Char)
        Q = maxsuffixpal(maxsuffix, a)
        creatednode = !haskey(Q.edges, a)
        if creatednode
            P = sizednode(Q.sz + 2)
            push!(nodes, P)
            if P.sz == 1
                P.link = evenroot
            else
                P.link = maxsuffixpal(Q.link, a).edges[a]
            end
            Q.edges[a] = P            # adds edge (Q, P)
        end
        maxsuffix = Q.edges[a]        # P becomes the new maxsuffix
        S *= string(a)
        creatednode
    end

    function getsubpalindromes()
        result = Vector{String}()
        getsubpalindromes(oddroot, [oddroot], "", result)
        getsubpalindromes(evenroot, [evenroot], "", result)
        result
    end

    function getsubpalindromes(nd, nodestohere, charstohere, result)
        for (lnkname, nd2) in nd.edges
            getsubpalindromes(nd2, vcat(nodestohere, nd2), charstohere * lnkname, result)
        end
        if nd !== oddroot && nd !== evenroot
            assembled = reverse(charstohere) *
                (nodestohere[1] === evenroot ? charstohere : charstohere[2:end])
            push!(result, assembled)
        end
    end

    println("Results of processing string \"$str\":")
    for c in str
        addchar(c)
    end
    println("Number of sub-palindromes: ", length(nodes))
    println("Sub-palindromes: ", getsubpalindromes())
end

eertree("eertree")

Output:

Results of processing string "eertree":
Number of sub-palindromes: 7
Sub-palindromes: ["e", "r", "eertree", "ertre", "rtr", "t", "ee"]

Kotlin

Translation of: Python

// version 1.1.4

class Node {
    val edges = mutableMapOf<Char, Node>()  // edges (or forward links)
    var link: Node? = null                  // suffix link (backward links)
    var len = 0                             // the length of the node
}

class Eertree(str: String) {
    val nodes = mutableListOf<Node>()

    private val rto = Node()                // odd length root node, or node -1
    private val rte = Node()                // even length root node, or node 0
    private val s = StringBuilder("0")      // accumulated input string, T = S[1..i]
    private var maxSufT = rte               // maximum suffix of tree T

    init {
        // Initialize and build the tree
        rte.link = rto
        rto.link = rte
        rto.len  = -1
        rte.len  = 0
        for (ch in str) add(ch)
    }

    private fun getMaxSuffixPal(startNode: Node, a: Char): Node {
        // 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
        val i = s.length
        var k = u.len
        while (u !== rto && s[i - k - 1] != a) {
            if (u === u.link!!) throw RuntimeException("Infinite loop detected")
            u = u.link!!
            k = u.len
        }
        return u
    }

    private fun add(a: Char): Boolean {
        // 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)
        val q = getMaxSuffixPal(maxSufT, a)

        // We check Q to see whether it has an outgoing edge labeled by a.
        val createANewNode = a !in q.edges.keys

        if (createANewNode) {
            // We create the node P of length Q + 2
            val p = Node()
            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.append(a)

        return createANewNode
    }

    fun getSubPalindromes(): List<String> {
        // Traverse tree to find sub-palindromes
        val result = mutableListOf<String>()
        // Odd length words
        getSubPalindromes(rto, listOf(rto), "", result)
        // Even length words
        getSubPalindromes(rte, listOf(rte), "", result)
        return result
    }

    private fun getSubPalindromes(nd: Node, nodesToHere: List<Node>,
                          charsToHere: String, result: MutableList<String>) {
        // 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, nd2) in nd.edges) {
            getSubPalindromes(nd2, nodesToHere + nd2, charsToHere + lnkName, result)
        }

        // Reconstruct based on charsToHere characters.
        if (nd !== rto && nd !== rte) { // Don't print for root nodes
            val assembled = charsToHere.reversed() +
                if (nodesToHere[0] === rte)  // Even string
                    charsToHere
                else  // Odd string
                    charsToHere.drop(1)
            result.add(assembled)
        }
    }
}

fun main(args: Array<String>) {
    val str = "eertree"
    println("Processing string '$str'")
    val eertree = Eertree(str)
    println("Number of sub-palindromes: ${eertree.nodes.size}")
    val result = eertree.getSubPalindromes()
    println("Sub-palindromes: $result")
}

Output:

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

M2000 Interpreter

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"))

Output:

("ee", "e", "r", "t", "rtr", "ertre", "eertree")

Nim

Translation of: Kotlin

import algorithm, strformat, strutils, tables

type

  Node = ref object
    edges: Table[char, Node]  # Edges (forward links).
    link: Node                # Suffix link (backward link).
    len: int                  # Length of the node.

  Eertree = object
    nodes: seq[Node]
    rto: Node                 # Odd length root node or node -1.
    rte: Node                 # Even length root node or node 0.Node
    str: string               # Accumulated input string.
    maxSuf: Node              # Maximum suffix.

#---------------------------------------------------------------------------------------------------

func initEertree(): Eertree =
  ## Create and initialize an eertree.
  result = Eertree(rto: Node(len: - 1), rte: Node(len: 0))
  result.rto.link = result.rto
  result.rte.link = result.rto
  result.str = "0"
  result.maxSuf = result.rte

#---------------------------------------------------------------------------------------------------

func getMaxSuffixPal(tree: Eertree; startNode: Node; ch: char): Node =
  ## We traverse the suffix-palindromes of "tree" in the order of decreasing length.
  ## For each palindrome we read its length "k" and compare "tree[i-k]" against "ch"
  ## until we get an equality or arrive at the -1 node.

  result = startNode
  let i = tree.str.high
  while result != tree.rto and tree.str[i - result.len] != ch:
    doAssert(result != result.link, "circular reference above odd root")
    result = result.link

#---------------------------------------------------------------------------------------------------

func add(tree: var Eertree; ch: char): bool =
  ## 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).

  let q = tree.getMaxSuffixPal(tree.maxSuf, ch)

  # We check "q" to see whether it has an outgoing edge labeled by "ch".
  result = ch notin q.edges

  if result:
    # We create the node "p" of length "q.len + 2"
    let p = Node()
    tree.nodes.add(p)
    p.len = q.len + 2
    if p.len == 1:
      # If p = ch, create the suffix link (p, 0).
      p.link = tree.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 = tree.getMaxSuffixPal(q.link, ch).edges[ch]
    # Create the edge "(q, p)".
    q.edges[ch] = p

  # "p" becomes the new maxSuf.
  tree.maxSuf = q.edges[ch]

  # Store accumulated input string.
  tree.str.add(ch)

#---------------------------------------------------------------------------------------------------

func getSubPalindromes(tree: Eertree; node: Node;
                       nodesToHere: seq[Node]; charsToHere: string;
                       result: var seq[string]) =
  ## 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 linkName, node2 in node.edges.pairs:
    tree.getSubPalindromes(node2, nodesToHere & node2, charsToHere & linkName, result)

  # Reconstruct based on charsToHere characters.
  if node notin [tree.rto, tree.rte]:
    # Don’t print for root nodes.
    let assembled = reversed(charsTohere).join() &
                    (if nodesToHere[0] == tree.rte: charsToHere
                     else: charsToHere[1..^1])
    result.add(assembled)

#---------------------------------------------------------------------------------------------------

func getSubPalindromes(tree: Eertree): seq[string] =
  ## Traverse tree to find sub-palindromes.

  # Odd length words
  tree.getSubPalindromes(tree.rto, @[tree.rto], "", result)
  # Even length words
  tree.getSubPalindromes(tree.rte, @[tree.rte], "", result)

#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:
  const Str = "eertree"
  echo fmt"Processing string: '{Str}'"
  var eertree = initEertree()
  for ch in Str:
    discard eertree.add(ch)
  echo fmt"Number of sub-palindromes: {eertree.nodes.len}"
  let result = eertree.getSubPalindromes()
  echo fmt"Sub-palindromes: {result.join("", "")}"

Output:

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

Objeck

Translation of: Java

use Collection.Generic;

class Eertree {
  function : Main(args : String[]) ~ Nil {
    tree := GetEertree("eertree");
    Show(SubPalindromes(tree));
  }

  function : GetEertree(s : String) ~ Vector<Node> {
    tree := Vector->New()<Node>;
    tree->AddBack(Node->New(0, Nil, 1));
    tree->AddBack(Node->New(-1, Nil, 1));
    suffix := 1;
    
    n : Int; k : Int;
    for(i := 0; i < s->Size(); ++i;) {
      c := s->Get(i);

      done := false;
      for (j := suffix; <>done; j := tree->Get(j)->GetSuffix();) {      
        k := tree->Get(j)->GetLength();
        b := i - k - 1;
        if (b >= 0 & s->Get(b) = c) {
          n := j;      
          done := true;
        };
      };
      skip := false;
      if (tree->Get(n)->GetEdges()->Has(c)) {
        suffix := tree->Get(n)->GetEdges()->Find(c)->Get();
        skip := true;
      };

      if(<>skip) {         
        suffix := tree->Size();
        tree->AddBack(Node->New(k + 2));
        tree->Get(n)->GetEdges()->Insert(c, suffix);
        if (tree->Get(suffix)->GetLength() = 1) {
          tree->Get(suffix)->SetSuffix(0);
          skip := true;
        };

        if(<>skip) {
          done := false;
          while (<>done) {
            n := tree->Get(n)->GetSuffix();
            b := i - tree->Get(n)->GetLength() - 1;
            if (b >= 0 & s->Get(b) = c) {
              done := true;
            };
          };
          tree->Get(suffix)->SetSuffix(tree->Get(n)->GetEdges()->Find(c)->Get());
        };          
      };
    };

    return tree;
  }

  function : SubPalindromes(tree : Vector<Node>) ~ Vector<String> {
    s := Vector->New()<String>;
    SubPalindromesChildren(0, "", tree, s);

    keys := tree->Get(1)->GetEdges()->GetKeys()<CharHolder>;
    each(k : keys) {
      key := keys->Get(k);
      str := key->Get()->ToString();
      s->AddBack(str);
      value := tree->Get(1)->GetEdges()->Find(key)->As(IntHolder)->Get();
      SubPalindromesChildren(value, str, tree, s);
    };

    return s;
  }

  function : SubPalindromesChildren(n : Int, p : String, tree : Vector<Node>, s : Vector<String>)  ~ Nil {
    keys := tree->Get(n)->GetEdges()->GetKeys()<CharHolder>;
    each(k : keys) {
      key := keys->Get(k);
      c := key->Get();
      value := tree->Get(n)->GetEdges()->Find(key)->As(IntHolder)->Get();
      str := ""; str += c; str += p; str += c;
      s->AddBack(str);
      SubPalindromesChildren(value, str, tree, s);
    };    
  }

  function : Show(result : Vector<String>) ~ Nil {
    out := "[";
    each(i : result) {
      out += result->Get(i);
      if(i + 1 < result->Size()) {
        out += ", ";
      };
    };
    out += "]";
    out->PrintLine();
  }
}

class Node {
  @length : Int;
  @edges : Map<CharHolder, IntHolder>;
  @suffix : Int;

  New(length : Int, edges : Map<CharHolder, IntHolder>, suffix : Int) {
    @length := length;
    @edges := edges <> Nil ? edges : Map->New()<CharHolder, IntHolder>;
    @suffix := suffix;
  }

  New(length : Int) {
    @length := length;
    @edges := Map->New()<CharHolder, IntHolder>;
  }

  method : public : GetLength() ~ Int {
    return @length;
  }

  method : public : GetSuffix() ~ Int {
    return @suffix;
  }

  method : public : SetSuffix(suffix : Int) ~ Nil {
    @suffix := suffix;
  }

  method : public : GetEdges() ~ Map<CharHolder, IntHolder> {
    return @edges;
  }
}

Output:

[ee, e, r, t, rtr, ertre, eertree]

Perl

Translation of: Raku

$str = "eertree";

for $n (1 .. length($str)) {
   for $m (1 .. length($str)) {
      $strrev = "";
      $strpal = substr($str, $n-1, $m);
      if ($strpal ne "") {
         for $p (reverse 1 .. length($strpal)) {
            $strrev .= substr($strpal, $p-1, 1);
         }
         ($strpal eq $strrev) and push @pal, $strpal;
      }
   }
}

print join ' ', grep {not $seen{$_}++} @pal, "\n";

Output:

e ee eertree ertre r rtr t

Phix

If you use this in anger it may be wise to replace {string chars, sequence next} with a dictionary, which can obviously be either a new dictionary for each node, or perhaps better a single/per tree dictionary keyed on {n,ch}.

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()

Output:

The tree matches Fig 1 in the pdf linked above.

tree:
[1]: len:-1  suffix:1  chars:ert   next:{3,5,6}
[2]: len: 0  suffix:1  chars:e     next:{4}
[3]: len: 1  suffix:2  chars:      next:{}
[4]: len: 2  suffix:3  chars:      next:{}
[5]: len: 1  suffix:2  chars:      next:{}
[6]: len: 1  suffix:2  chars:r     next:{7}
[7]: len: 3  suffix:5  chars:e     next:{8}
[8]: len: 5  suffix:3  chars:e     next:{9}
[9]: len: 7  suffix:4  chars:      next:{}

{"e","r","t","rtr","ertre","eertree","ee"}

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)

Output:

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

Racket

Translation of: Python

#lang racket
(struct node (edges ; edges (or forward links)
              link ; suffix link (backward links)
              len) ; the length of the node 
  #:mutable)

(define (new-node link len) (node (make-hash) link len))

(struct eertree (nodes
                 rto ; odd length root node, or node -1
                 rte ; even length root node, or node 0
                 S ; accumulated input string, T=S[1..i]
                 max-suf-t) ; maximum suffix of tree T
  #:mutable)

(define (new-eertree)
  (let* ((rto (new-node #f -1))
         (rte (new-node rto 0)))
    (eertree null rto rte (list 0) rte)))

(define (eertree-get-max-suffix-pal et start-node 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. |#
  (match et
    [(eertree nodes rto rte (and S (app length i)) max-suf-t)
     (let loop ((u start-node))
       (let ((k (node-len u)))
         (if (or (eq? u rto) (= (list-ref S (- i k 1)) a))
             u
             (let ((u→ (node-link u)))
               (when (eq? u u→) (error 'eertree-get-max-suffix-pal "infinite loop"))
               (loop u→)))))]))

(define (eertree-add! et 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) |#
  (match (eertree-get-max-suffix-pal et (eertree-max-suf-t et) a)
    [(node Q.edges Q.→ Q.len) 
     ;; We check Q to see whether it has an outgoing edge labeled by a.
     (define new-node? (not (hash-has-key? Q.edges a)))
     (when new-node?
       (define P (new-node #f (+ Q.len 2))) ; We create the node P of length Q+2
       (set-eertree-nodes! et (append (eertree-nodes et) (list P)))
       (define P→
         (if (= (node-len P) 1)
             (eertree-rte et) ; if P = a, create the suffix link (P,0)
             ;; It remains to c reate the suffix link from P if |P|>1.
             ;; Just continue traversing suffix-palindromes of T starting with the suffix link of Q.
             (hash-ref (node-edges (eertree-get-max-suffix-pal et Q.→ a)) a)))
       (set-node-link! P P→)
       (hash-set! Q.edges a P)) ; create the edge (Q,P)
     
     (set-eertree-max-suf-t! et (hash-ref Q.edges a)) ; P becomes the new maxSufT
     (set-eertree-S! et (append (eertree-S et) (list a))) ; Store accumulated input string
     new-node?]))

(define (eertree-get-sub-palindromes et)
  (define (inr nd (node-path (list nd)) (char-path/rev null))
    ;; Each node represents a palindrome, which can be reconstructed by the path from the root node to
    ;; each non-root node.
    (let ((deeper ; Traverse all edges, since they represent other palindromes     
           (for/fold ((result null)) (([→-name nd2] (in-hash (node-edges nd))))
             ; The lnk-name is the character used for this edge
             (append result (inr nd2 (append node-path (list nd2)) (cons →-name char-path/rev)))))
          (root-node? (or (eq? (eertree-rto et) nd) (eq? (eertree-rte et) nd))))
      (if root-node? ; Don't add root nodes
          deeper
          (let ((even-string? (eq? (car node-path) (eertree-rte et)))
                (char-path (reverse char-path/rev)))
            (cons (append char-path/rev (if even-string? char-path (cdr char-path))) deeper)))))
  inr)

(define (eertree-get-palindromes et)
  (define sub (eertree-get-sub-palindromes et))
  (append (sub (eertree-rto et))
          (sub (eertree-rte et))))

(module+ main
  (define et (new-eertree))
  ;; eertree works in integer space, so we'll map to/from char space here
  (for ((c "eertree")) (eertree-add! et (char->integer c)))
  (map (compose list->string (curry map integer->char)) (eertree-get-palindromes et)))

Output:

'("t" "rtr" "ertre" "eertree" "r" "e" "ee")

Raku

(formerly Perl 6)

Translation of: Ring

my $str = "eertree";
my @pal = ();
my ($strrev,$strpal);

for (1 .. $str.chars) -> $n {
   for (1 .. $str.chars) -> $m {
      $strrev = "";
      $strpal = $str.substr($n-1, $m);
      if ($strpal ne "") {
         for ($strpal.chars ... 1) -> $p {
            $strrev ~= $strpal.substr($p-1,1);
         }
         ($strpal eq $strrev) and @pal.push($strpal);
      }
   }
}

say @pal.unique;

Output:

(e ee eertree ertre r rtr t)

REXX

This REXX program is modeled after the   Ring   example.

/*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. */

output   when using the default input:

──────── The input string that is being used:  eertree
──────── The number of sub─palindromes found:  7
──────── The  list  of sub─palindromes found:  e  ee  eertree  ertre  r  rtr  t

Ring

# Project : Eertree

str = "eertree"
pal = []
for n=1 to len(str)
    for m=1 to len(str)
        strrev = ""
        strpal = substr(str, n, m)
        if strpal != ""
           for p=len(strpal) to 1 step -1
               strrev = strrev + strpal[p]
           next
           if strpal = strrev 
              add(pal, strpal)
           ok
        ok
    next
next 
sortpal = sort(pal)
for n=len(sortpal) to 2 step -1
    if sortpal[n] = sortpal[n-1]
       del(sortpal, n)
    ok
next
see sortpal + nl

Output:

e
ee
eertree
ertre
r
rtr
t

Ruby

Translation of: D

class Node
    def initialize(length, edges = {}, suffix = 0)
        @length = length
        @edges = edges
        @suffix = suffix
    end

    attr_reader :length
    attr_reader :edges
    attr_accessor :suffix
end

EVEN_ROOT = 0
ODD_ROOT = 1

def eertree(s)
    tree = [
        Node.new(0, {}, ODD_ROOT),
        Node.new(-1, {}, ODD_ROOT)
    ]
    suffix = ODD_ROOT
    s.each_char.with_index { |c, i|
        n = suffix
        k = 0
        loop do
            k = tree[n].length
            b = i - k - 1
            if b >= 0 and s[b] == c then
                break
            end
            n = tree[n].suffix
        end
        if tree[n].edges.key?(c) then
                suffix = tree[n].edges[c]
            next
        end
        suffix = tree.length
        tree << Node.new(k + 2)
        tree[n].edges[c] = suffix
        if tree[suffix].length == 1 then
            tree[suffix].suffix = 0
            next
        end
        loop do
            n = tree[n].suffix
            b = i - tree[n].length - 1
            if b >= 0 and s[b] == c then
                break
            end
        end
        tree[suffix].suffix = tree[n].edges[c]
    }
    return tree
end

def subPalindromes(tree)
    s = []

    children = lambda { |n,p,f|
        for c,v in tree[n].edges
            m = tree[n].edges[c]
            p = c + p + c
            s << p
            f.call(m, p, f)
        end
    }

    children.call(0, '', children)

    for c,n in tree[1].edges
        s << c
        children.call(n, c, children)
    end

    return s
end

tree = eertree("eertree")
print subPalindromes(tree), "\n"

Output:

["ee", "e", "r", "t", "rtr", "ertre", "eertree"]

Rust

Translation of: Go

use std::collections::HashMap;
use std::convert::TryInto;

struct Node {
    length: isize,
    edges: HashMap<u8, usize>,
    suffix: usize,
}

impl Node {
    fn new(length: isize, suffix: usize) -> Self {
        Node {
            length,
            suffix,
            edges: HashMap::new(),
        }
    }
}

const EVEN_ROOT: usize = 0;
const ODD_ROOT: usize = 1;

fn eertree(s: &[u8]) -> Vec<Node> {
    let mut tree = vec![
        Node::new(0, ODD_ROOT), // even root
        Node::new(-1, ODD_ROOT), // odd root
    ];

    let mut suffix = ODD_ROOT;

    for (i, &c) in s.iter().enumerate() {
        let mut n = suffix;
        let mut k;

        loop {
            k = tree[n].length;
            let k_plus_one: usize = (k + 1).try_into().unwrap_or(0);
            if let Some(b) = i.checked_sub(k_plus_one) {
                if b < s.len() && s[b] == c {
                    break;
                }
            }
            n = tree[n].suffix;
        }

        if tree[n].edges.contains_key(&c) {
            suffix = tree[n].edges[&c];
            continue;
        }

        suffix = tree.len();
        tree.push(Node::new(k + 2, 0));
        tree[n].edges.insert(c, suffix);

        if tree[suffix].length == 1 {
            tree[suffix].suffix = EVEN_ROOT;
            continue;
        }

        loop {
            n = tree[n].suffix;
            let tree_n_length_plus_one: usize = (tree[n].length + 1).try_into().unwrap_or(0);
            if let Some(b) = i.checked_sub(tree_n_length_plus_one) {
                if b < s.len() && s[b] == c {
                    break;
                }
            }
        }

        tree[suffix].suffix = tree[n].edges[&c];
    }

    tree
}

fn sub_palindromes(tree: &[Node]) -> Vec<String> {
    let mut result = Vec::new();
    fn children(node: usize, p: String, tree: &[Node], result: &mut Vec<String>) {
        for (&c, &n) in &tree[node].edges {
            let c = c as char;
            let p_new = format!("{}{}{}", c, p, c);
            result.push(p_new.clone());
            children(n, p_new, tree, result);
        }
    }

    children(EVEN_ROOT, String::new(), tree, &mut result);

    for (&c, &n) in &tree[ODD_ROOT].edges {
        let c = c as char;
        let p = c.to_string();
        result.push(p.clone());
        children(n, p, tree, &mut result);
    }

    result
}

fn main() {
    let tree = eertree(b"eertree");
    let palindromes = sub_palindromes(&tree);
    for palindrome in palindromes {
        println!("{}", palindrome);
    }
}

Output:

ee
e
t
rtr
ertre
eertree
r

Visual Basic .NET

Translation of: C#

Module Module1

    Class Node
        Public Sub New(Len As Integer)
            Length = Len
            Edges = New Dictionary(Of Char, Integer)
        End Sub

        Public Sub New(len As Integer, edg As Dictionary(Of Char, Integer), suf As Integer)
            Length = len
            Edges = If(IsNothing(edg), New Dictionary(Of Char, Integer), edg)
            Suffix = suf
        End Sub

        Property Edges As Dictionary(Of Char, Integer)
        Property Length As Integer
        Property Suffix As Integer
    End Class

    ReadOnly EVEN_ROOT As Integer = 0
    ReadOnly ODD_ROOT As Integer = 1

    Function Eertree(s As String) As List(Of Node)
        Dim tree As New List(Of Node) From {
            New Node(0, New Dictionary(Of Char, Integer), ODD_ROOT),
            New Node(-1, New Dictionary(Of Char, Integer), ODD_ROOT)
        }
        Dim suffix = ODD_ROOT
        Dim n As Integer
        Dim k As Integer

        For i = 1 To s.Length
            Dim c = s(i - 1)
            n = suffix
            While True
                k = tree(n).Length
                Dim b = i - k - 2
                If b >= 0 AndAlso s(b) = c Then
                    Exit While
                End If
                n = tree(n).Suffix
            End While
            If tree(n).Edges.ContainsKey(c) Then
                suffix = tree(n).Edges(c)
                Continue For
            End If
            suffix = tree.Count
            tree.Add(New Node(k + 2))
            tree(n).Edges(c) = suffix
            If tree(suffix).Length = 1 Then
                tree(suffix).Suffix = 0
                Continue For
            End If
            While True
                n = tree(n).Suffix
                Dim b = i - tree(n).Length - 2
                If b >= 0 AndAlso s(b) = c Then
                    Exit While
                End If
            End While
            Dim a = tree(n)
            Dim d = a.Edges(c)
            Dim e = tree(suffix)
            e.Suffix = d
        Next

        Return tree
    End Function

    Function SubPalindromes(tree As List(Of Node)) As List(Of String)
        Dim s As New List(Of String)
        Dim children As Action(Of Integer, String) = Sub(n As Integer, p As String)
                                                         For Each c In tree(n).Edges.Keys
                                                             Dim m = tree(n).Edges(c)
                                                             Dim p1 = c + p + c
                                                             s.Add(p1)
                                                             children(m, p1)
                                                         Next
                                                     End Sub
        children(0, "")
        For Each c In tree(1).Edges.Keys
            Dim m = tree(1).Edges(c)
            Dim ct = c.ToString()
            s.Add(ct)
            children(m, ct)
        Next
        Return s
    End Function

    Sub Main()
        Dim tree = Eertree("eertree")
        Dim result = SubPalindromes(tree)
        Dim listStr = String.Join(", ", result)
        Console.WriteLine("[{0}]", listStr)
    End Sub

End Module

Output:

[ee, e, r, t, rtr, ertre, eertree]

Wren

Translation of: Kotlin

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)")

Output:

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

zkl

Translation of: Python

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);
      }
   }
}

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

Output:

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