def next_char(stream):
    for c in stream:
        yield c


def create_trie(words):
    root = dict()
    for word in words:
        node = root
        for w in word:
            node = node.setdefault(w, {})
        node['END'] = 'END'
    return root


def count_words(s, words):
    trie = create_trie(words)
    stored_keys = []
    counters = {word: 0 for word in words}

    for s in next_char(s):
        # Compare with store keys
        for k in [x for x in stored_keys if len(x) > 0]:
            # Go to the current level
            trie_level = trie  # root
            word = ''
            for level in k:
                word += level
                trie_level = trie_level[level]  # Go to next level

            # What do we've on this level
            if s in trie_level.keys():
                #Check next if it ends
                if 'END' in trie_level[s]:
                    counters[word+s] += 1
                    k.clear()
                else:
                    k.append(s)
            else:  # Doesn't match
                k.clear()

        # Compare with root
        if s in trie.keys():
            stored_keys.append([s])

    return counters

if __name__ == '__main__':
    stream = 'acacabcatghhellomvnsdb'
    words = ["aca","cat","hello","world"]
    print(count_words(stream, words))