All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Prasanjeet verma and his sorrow
/
No tags
Problem
Editorial
Analytics

enter image description here

The problem setter wants to annoy prasanjeet by asking him a tough problem of data structure but prasanjeet doesn't know any such thing. He comes to Sanaya, his girlfriend to ask for help and Sanaya wants you to solve it for him. We have a dictionary that we are going to create everytime we add a word in it and this task is denoted by "add word" and later we try to find out the number of words in dictionary with the prefix which is denoted by "find prefix". We are given the value of n which simply means the number of tasks we perform and it is the first line. The next n lines contains tasks to performed as stated above either as "add word" or "find prefix".Note the " is just for making it clear .

Input Format

The first line contains a single integer n , denoting the number of operations to perform. Each line i of the n subsequent lines contains an operation in one of the two forms defined above.

Constraint:

1<=n<=10^5

1<=|name|<=21

1<=|partial|<=21

It is guaranteed that name and partial contain lowercase English letters only. The input doesn't have any duplicate name for the add operation.

Output Format <>

For each find partial operation, print the number of contact names starting with partial on a new line.

SAMPLE INPUT
4
add hack
add hackerearth
find hac
find hak
SAMPLE OUTPUT
2
0
Explanation

We perform the following sequence of operations:

Add a contact named hack. Add a contact named hackerearth. Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we "2" print on a new line. Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print "0" on a new line.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?