# https://www.infoarena.ro/problema/trie


# 0 w - adauga o aparitie a cuvantului w in lista
# 1 w - sterge o aparitie a cuvantului w din lista
# 2 w - tipareste numarul de aparitii ale cuvantului w in lista
# 3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista

# redirect to file all prints
import sys
sys.stdout=open("trie.out","w")

class Trie:
    def __init__(self):
        # what is root?

        self.root = {}
        self.endOfWordSymbol = "*"

    def add(self, word):
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]

        if self.endOfWordSymbol in node.keys():
            node[self.endOfWordSymbol] += 1
        else:
            node[self.endOfWordSymbol] = 1

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return 0
            node = node[char]
        return node[self.endOfWordSymbol] if self.endOfWordSymbol in node else 0

    def delete(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return "cant delete because it does not exist"
            node = node[char]

        if self.endOfWordSymbol in node.keys():
            if node[self.endOfWordSymbol] > 0:
                node[self.endOfWordSymbol] -= 1

    def longest_prefix(self, word):
        node = self.root
        prefix = ""
        for char in word:
            if self.endOfWordSymbol in node.keys() and node[self.endOfWordSymbol] == 0:
                return len(prefix) - 1
            if char not in node:
                return len(prefix)

            prefix += char
            node = node[char]

    def print_trie(self):
        print(self.root)


# driver code:
if __name__ == "__main__":
    trie = Trie()
    file = open("trie.in", "r")

    for line in file:
        command, word = line.split()
        if command == "0":
            trie.add(word)
        elif command == "1":
            trie.delete(word)
        elif command == "2":
            print(trie.search(word))
        elif command == "3":
            print(trie.longest_prefix(word))
        else:
            print("Invalid command")
    # print(trie.print_trie())