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.


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