How to resolve the algorithm Eertree step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Eertree step by step in the C# programming language

Table of Contents

Problem Statement

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.

Construct an eertree for the string "eertree", then output all sub-palindromes by traversing the tree.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Eertree step by step in the C# programming language

Eertree Algorithm

The provided C# code implements the Eertree algorithm for finding palindromic substrings in a given string. The Eertree, also known as a palindromic tree, is a tree data structure that represents all the palindromic substrings of a string in a compact and efficient way.

Node Class:

The Node class represents a node in the Eertree:

  • Length: The length of the longest palindromic substring ending at this node.
  • Edges: A dictionary mapping characters to the indices of child nodes.
  • Suffix: The index of the parent node representing the longest suffix of the current node's palindromic substring.

Eertree Function:

The Eertree function constructs the Eertree for a given string s:

  • Initializes two root nodes with lengths 0 and -1, respectively.
  • Iterates through each character c in the string:
    • Searches for the longest suffix n of the current palindromic substring that matches the prefix ending at c.
    • If there is no edge for c from node n, a new node suffix is created and added to the tree.
    • Updates the suffix link of node suffix to the child node of node n that matches the prefix ending at c.
  • Returns the constructed Eertree.

SubPalindromes Function:

The SubPalindromes function generates a list of all distinct palindromic substrings from the Eertree:

  • Recursively explores the tree from the root nodes (0 and 1) and appends palindromes to the list s:
    • For each child node of the current node, forms a palindrome by concatenating the edge character with the parent palindrome (if any).
    • Continues exploring the child nodes recursively to find deeper palindromes.

Main Function:

  • Constructs the Eertree for the string "eertree".
  • Generates a list of palindromic substrings from the Eertree.
  • Prints the list of palindromic substrings.

Example Output:

The output for the string "eertree" should be:

[e, r, ee, err, erte, ert, etre, evre, re, rree, rtter, t, tte, tree]

Source code in the csharp programming language

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

You may also check:How to resolve the algorithm CSV to HTML translation step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Y combinator step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm Horizontal sundial calculations step by step in the Factor programming language
You may also check:How to resolve the algorithm Array concatenation step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm Pi step by step in the Mathematica / Wolfram Language programming language