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

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

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

In order to find the longest shared substring between Text1 and Text2, 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.

    TREECOLORING(ColoredTree)
        while ColoredTree has ripe nodes
            for each ripe node v in ColoredTree
                if there exist differently colored children of v
                    Color(v) ← "purple"
                else
                    Color(v) ← color of all children of v
        return ColoredTree

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', [])])])])