Example use of Trie to find substring matches

gistfile1.py

#!/usr/bin/env python
# pylint: disable=C0111, R0903


class Trie(object):
    def __init__(self):
        self.children = {}

    def add_child(self, letter):
        if letter in self.children:
            return self.children[letter]
        else:
            child = Trie()
            self.children[letter] = child
            return child

    def traverse(self, letter):
        return self.children.get(letter, None)


def populate_trie(root, letters):
    current_positions = []
    for letter in letters:
        current_positions = [
            position.add_child(letter)
            for position in current_positions
        ]
        current_positions.append(root.add_child(letter))
    return root


class TrieSearch(object):
    def __init__(self, trie, starting_index):
        self.trie = trie
        self.starting_index = starting_index
        self.ending_index = starting_index + 1

    def update(self, letter):
        """ This returns a boolean indicating
            if the search can accept the letter """
        self.trie = self.trie.traverse(letter)
        if self.trie is not None:
            self.ending_index = self.ending_index + 1
            return True
        return False

    def get_match(self, letters):
        return letters[self.starting_index:self.ending_index]


def find_matches(root, letters):
    completed_matches = []
    current_matches = []

    for index, letter in enumerate(letters):
        new_current = []

        for current in current_matches:
            if current.update(letter):
                new_current.append(current)
            else:
                completed_matches.append(current)

        new_search_trie = root.traverse(letter)
        if new_search_trie is not None:
            new_current.append(TrieSearch(new_search_trie, index))

        current_matches = new_current
    all_matches = completed_matches + current_matches
    return [match.get_match(letters) for match in all_matches]


def run():
    fiveprime = "GATTCGAAGTCCACTATC"
    threeprime = "TGAGTAGGACGGCACTATC"
    root = Trie()
    populate_trie(root, fiveprime)
    populate_trie(root, threeprime)
    matches = find_matches(root, "CACTATCAAAAAAA")
    print matches


if __name__ == "__main__":
    run()