In “Find the Longest Substring Shared by Two Strings”¹, we introduced the Longest Shared Substring Problem. A naive approach for finding a longest shared substring of strings Text₁ and Text₂ would construct one suffix tree for Text₁ and another for Text₂. Instead, we will add "#" to the end of Text₁, add "$" to the end of Text₂, and then construct the single suffix tree for the concatenation of Text₁ and Text₂. We color a leaf in this suffix tree blue if it is labeled by the starting position of a suffix starting in Text₁; we color a leaf red if it is labeled by the starting position of a suffix starting in Text₂.

We also color the remaining nodes of the suffix tree blue, red, and purple according to the following rules:

• a node is colored blue or red if all leaves in its subtree (i.e., the subtree beneath it) are all blue or all red, respectively;
• a node is colored purple if its subtree contains both blue and red leaves.

We use Color(v) to denote the color of node v.

In order to find the longest shared substring between Text₁ and Text₂, we need to examine all purple nodes as well as the strings spelled by paths leading to the purple nodes. A longest such string yields a solution to the Longest Shared Substring Problem.

TREECOLORING, whose pseudocode is shown below, colors the nodes of a suffix tree from the leaves upward. This algorithm assumes that the leaves of the suffix tree have been labeled "blue" or "red" and all other nodes have been labeled "gray". A node in a tree is called ripe if it is gray but has no gray children.

Assignment

Implement the colored_tree_from_edges method which takes an adjacency dictionary and a dictionary from label to color.

The function should return an object of class ColoredTree which contains a label, a color and any amount of children as a list.
ColoredTree should have a __repr__(self) implementation and an init of the form __init__(self, label, color, children)

Example

>>> colored_tree_from_edges({0: {1}, 1: {2, 3, 4}, 2: set(), 3: {5, 6, 7}, 4: {8}, 5: set(), 6: set(), 7: {9, 10}, 8: set(), 9: set(), 10: set()}, {2: 'red', 5: 'blue', 6: 'red', 8: 'blue', 9: 'red', 10: 'red'})
ColoredTree(0, 'purple', [ColoredTree(1, 'purple', [ColoredTree(2, 'red', []), ColoredTree(3, 'purple', [ColoredTree(5, 'blue', []), ColoredTree(6, 'red', []), ColoredTree(7, 'red', [ColoredTree(9, 'red', []), ColoredTree(10, 'red', [])])]), ColoredTree(4, 'blue', [ColoredTree(8, 'blue', [])])])])

>>> colored_tree_from_edges({0: {1, 2}, 1: set(), 2: {3, 4, 5}, 3: {10, 11, 12}, 4: {13, 14}, 5: {8, 9, 6, 7}, 6: set(), 7: set(), 8: set(), 9: set(), 10: set(), 11: set(), 12: set(), 13: set(), 14: set()}, {1: 'blue', 6: 'blue', 7: 'red', 8: 'red', 9: 'blue', 10: 'red', 11: 'blue', 12: 'blue', 13: 'blue', 14: 'blue'})
ColoredTree(0, 'purple', [ColoredTree(1, 'blue', []), ColoredTree(2, 'purple', [ColoredTree(3, 'purple', [ColoredTree(10, 'red', []), ColoredTree(11, 'blue', []), ColoredTree(12, 'blue', [])]), ColoredTree(4, 'blue', [ColoredTree(13, 'blue', []), ColoredTree(14, 'blue', [])]), ColoredTree(5, 'purple', [ColoredTree(8, 'red', []), ColoredTree(9, 'blue', []), ColoredTree(6, 'blue', []), ColoredTree(7, 'red', [])])])])