Kickstart 2020 Round A

D.py

# Trie-based solution
# https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3
# Seems to be feasible solution with good efficicency, though unfortunately got WA in larger test


from sys import stdin, stdout


class TrieNode(object):
    def __init__(self, char: str):
        self.char = char
        self.children = []
        self.count = 0

    def __str__(self):
        return str({c.char: "({}){}".format(c.count, c) for c in self.children})


def trie_add(root, word: str):
    node = root
    for char in word:
        node.count += 1
        for child in node.children:
            if child.char == char:
                node = child
                break
        else:
            new_node = TrieNode(char)
            node.children.append(new_node)
            node = new_node
    node.count += 1


class Sol:
    def __init__(self, ss, k):
        self.ss = ss
        self.k = k

    @classmethod
    def input(cls):
        n, k = map(int, stdin.readline().split())
        ss = [stdin.readline().strip() for _ in range(n)]
        return cls(ss, k)

    def solve(self):
        root = TrieNode("*")
        for s in self.ss:
            trie_add(root, s)
        return self.calc(root) - root.count // self.k

    def calc(self, node: TrieNode):
        num_group = node.count // self.k
        if num_group == 0:
            return 0
        ret = num_group
        for c in node.children:
            ret += self.calc(c)
        return ret


if __name__ == "__main__":
    for t in range(int(stdin.readline())):
        print("Case #{}: {}".format(t + 1, Sol.input().solve()))