Performs search and replace on the given input string `seq` using
        the values stored in this trie.  This method uses a O(n**2)
        chart-parsing algorithm to find the optimal way of replacing
        matches in the input.

        Arguments:
        - `seq`:

def replace(self, seq):
        '''
        Performs search and replace on the given input string `seq` using
        the values stored in this trie.  This method uses a O(n**2)
        chart-parsing algorithm to find the optimal way of replacing
        matches in the input.

        Arguments:
        - `seq`:
        '''
        # #1: seq must be stored in a container with a len() function
        seq = list(seq)
        # chart is a (n-1) X (n) table
        # chart[0] represents all matches of length (0+1) = 1
        # chart[n-1] represents all matches/rewrites of length (n-1+1) = n
        # chart[0][0] represents a match of length 1 starting at character 0
        # chart[0][n-1] represents a match of length 1 starting at character n-1
        # cells in the chart are tuples:
        #    (score, list)
        # we initialise chart by filling in row 0:
        #    each cell gets assigned (0, char), where char is the character at
        #    the corresponding position in the input string
        chart = [ [None for _i in range(len(seq)) ] for _i in range(len(seq)) ]
        chart[0] = [(0, char) for char in seq]
        # now we fill in the chart using the results from the aho-corasick
        # string matches
        for (begin, length, value) in self.find_all(seq):
            chart[length-1][begin] = (length, value)
        # now we need to fill in the chart row by row, starting with row 1
        for row in range(1, len(chart)):
            # each row is 1 cell shorter than the last
            for col in range(len(seq) - row):
                # the entry in [row][col] is the choice with the highest score; to
                # find this, we must search the possible partitions of the cell
                #
                # things on row 2 have only one possible partition: 1 + 1
                # things on row 3 have two: 1 + 2, 2 + 1
                # things on row 4 have three: 1+3, 3+1, 2+2
                #
                # we assume that any pre-existing entry found by aho-corasick
                # in a cell is already optimal
                #print('scanning [{}][{}]'.format(row, col))
                if chart[row][col] is not None:
                    continue
                # chart[1][2] is the cell of matches of length 2 starting at
                # character position 2;
                # it can only be composed of chart[0][2] + chart[0][3]
                #
                # partition_point is the length of the first of the two parts
                # of the cell
                #print('cell[{}][{}] => '.format(row, col))
                best_score = -1
                best_value = None
                for partition_point in range(row):
                    # the two cells will be [partition_point][col] and
                    # [row - partition_point - 2][col+partition_point+1]
                    x1 = partition_point
                    y1 = col
                    x2 = row - partition_point - 1
                    y2 = col + partition_point + 1
                    #print('   [{}][{}] + [{}][{}]'.format(x1, y1, x2, y2))
                    s1, v1 = chart[x1][y1]
                    s2, v2 = chart[x2][y2]
                    # compute the score
                    score = s1 + s2
                    #print('   = {}  +  {}'.format((s1, v1), (s2, v2)))
                    #print('   = score {}'.format(score))
                    if best_score < score:
                        best_score = score
                        best_value = v1 + v2
                        chart[row][col] = (best_score, best_value)
                        #print('   sets new best score with value {}'.format(
                        #    best_value))
        # now the optimal solution is stored at the top of the chart
        return chart[len(seq)-1][0][1]