Given a string Text and Trie(Patterns), we can quickly check whether any string from Patterns matches a prefix of Text. To do so, we start reading symbols from the beginning of Text and see what string these symbols “spell” as we proceed along the path downward from the root of the trie, as illustrated in the figure below. For each new symbol in Text, if we encounter this symbol along an edge leading down from the present node, then we continue along this edge; otherwise, we stop and conclude that no string in Patterns matches a prefix of Text. If we make it all the way to a leaf, then the pattern spelled out by this path matches a prefix of Text.

This algorithm is called PREFIXTRIEMATCHING.

    PREFIXTRIEMATCHING(Text, Trie)
        symbol ← first letter of Text
        v ← root of Trie
        while forever
            if v is a leaf in Trie
                return the pattern spelled by the path from the root to v
            else if there is an edge (v, w) in Trie labeled by symbol
                symbol ← next letter of Text
                v ← w
            else
                output "no matches found"
                return

Assignment

Implement the prefix_trie_matching method which takes a list of string patterns and a string to match.

The function should return a Set of starting indices where any of the given patterns is embedded in the text.

Example

    >>> prefix_trie_matching(['ATCG','GGGT'], 'AATCGGGTTCAATCGGGGT')
{1, 4, 11, 15}