class TrieNode(object):
    def __init__(self, char: str):
        self.char = char
        self.children = dict()
        self.counter = 0

class Trie:
    def __init__(self):
        self.root = TrieNode("")
    def insert(self, word):
        node = self.root
        for char in word:
            if char in node.children:
                node = node.children[char]
            else:
                new_node = TrieNode(char)
                node.children[char] = new_node
                node = new_node
        # 何回単語が挿入されたかを検知する
        node.counter += 1

    def dfs(self, node, prefix, output):
        if len(node.children) == 0:
            output.append((prefix + node.char, node.counter))
        for child in node.children.values():
            self.dfs(child, prefix + node.char, output)

    def query(self, x):
        output = []
        node = self.root
        # クエリの文だけ先にnodeを深ぼる
        for char in x:
            if char in node.children:
                node = node.children[char]
            else:
                return []
        # 末尾を消す(childrenの参照のときに繰り返してしまうから)
        self.dfs(node, x[:-1], output)
        return output

t = Trie()
t.insert("was")
t.insert("word")
t.insert("war")
t.insert("what")
t.insert("where")
t.insert("where")
assert t.query("wh") == [('what', 1), ('where', 2)]
assert t.query("w") == [('was', 1), ('war', 1), ('word', 1), ('what', 1), ('where', 2)]