To solve this problem, we need to assign a unique identifier to each team such that the identifier is the shortest possible prefix of the team's name that distinguishes it from all others. If a team's name is a prefix of another team's name, the identifier for the shorter name will be the full name itself.

Approach

1. Trie Data Structure: We use a trie (prefix tree) to efficiently track the frequency of each prefix of the team names. Each node in the trie keeps a count of how many times the prefix up to that node has been encountered.
2. Insertion: Insert all team names into the trie, incrementing the count of each node as we traverse through the characters of the name.
3. Find Shortest Unique Prefix: For each team name, traverse the trie again to find the shortest prefix where the count of the node is 1 (indicating this prefix is unique). If no such prefix exists (i.e., the name is a prefix of another name), the identifier is the full name.

Solution Code

n = int(input())
names = [input().strip() for _ in range(n)]

# Build the trie
root = {'count': 0, 'children': {}}
for name in names:
    current = root
    for c in name:
        if c not in current['children']:
            current['children'][c] = {'count': 0, 'children': {}}
        current = current['children'][c]
        current['count'] += 1

# Find the shortest unique prefix for each name
for name in names:
    current = root
    k = 0
    for c in name:
        current = current['children'][c]
        k += 1
        if current['count'] == 1:
            break
    print(name[:k])

Explanation

1. Trie Construction: The trie is built by iterating over each character of each team name. Each node in the trie represents a character in the prefix, and the count at each node tells us how many names have that prefix.
2. Prefix Identification: For each name, we traverse the trie until we find the first node where the count is 1. This node corresponds to the shortest unique prefix. If we reach the end of the name without finding such a node, the full name is the identifier (since it is a prefix of another name).

This approach efficiently handles the problem with a time complexity of O(L) per name, where L is the average length of the team names, making it suitable for large inputs. The trie structure ensures that we can quickly find the shortest unique prefix for each name.

作者声明:本文包含人工智能生成内容。