Contact Manager Search

You are tasked with implementing a contact manager that supports two types of operations:

1. add name: Add the contact name to your data structure.
2. find partial: Return the number of contact names that start with the given partial string.

The contact manager should efficiently handle a large list of operations. Your solution should consider optimal time complexity for both adding and finding contacts.

Input Format

You will receive a list of operations where each operation is in one of the two forms:

• add name: where name consists of lowercase English letters.
• find partial: where partial is a prefix string consisting of lowercase English letters.

For example:

add hack
add hacker
find hac
find hak

Output Format

For each find operation, print a number on a new line representing the count of names with the given prefix. For the sample input above, the expected output would be:

2
0

Constraints

• The number of operations can be large. Design your solution to be efficient in terms of both time and space.
• Names and partials consist only of lowercase English letters.
• You can assume that the operations are provided in a sequential manner.

Implement the contact manager based on the above description.