This is a partial judge problem. You only need to implement the required functions. The judge will provide main.c and function.h, read the input, call your functions, and check the output.
Before submitting your code:
Otherwise, you may receive a Compile Error.
You need to maintain a multiset of lowercase English strings. All strings consist only of lowercase English letters a to z. The same string may be inserted multiple times. Each occurrence is counted separately.
You need to implement a trie, also called a prefix tree, to support the following functions.
A trie is a tree data structure for storing strings. Each edge represents one character. A path from the root to a node represents a prefix.
For example, suppose the current strings are:
app
apple
ape
bat
The trie can be visualized as follows:
root
|-- a
| `-- p
| |-- p (app)
| | `-- l
| | `-- e (apple)
| `-- e (ape)
`-- b
`-- a
`-- t (bat)
In this trie, the prefix ap is shared by app, apple, and ape. Therefore, there are 3 strings with prefix ap.
The header file defines a trie node as follows:
typedef struct Node {
int pass_count;
int end_count;
struct Node *child[26];
} Node;
The value pass_count is useful for prefix counting. The value end_count is useful for checking whether the current path is a complete string.
The judge provides the following function:
Node* create_node(void);
This function creates and returns a new empty trie node. The judge's main.c will call this function once to create the root before any operation is processed. You may also call this function inside insert_string when a new child node is needed. You do not need to implement create_node.
Insert one occurrence of string s into the multiset.
void insert_string(Node *root, char s[]);
The string s contains only lowercase English letters.
Delete one occurrence of string s from the multiset.
void delete_string(Node *root, char s[]);
It is guaranteed that at least one occurrence of s currently exists.
Return the number of strings currently in the multiset that have p as a prefix.
int count_prefix(Node *root, char p[]);
Write the lexicographically smallest string currently in the multiset into ans.
void get_min_string(Node *root, char ans[]);
It is guaranteed that the multiset is not empty when this function is called. The output string must be null-terminated.
Write the lexicographically largest string currently in the multiset into ans.
void get_max_string(Node *root, char ans[]);
It is guaranteed that the multiset is not empty when this function is called. The output string must be null-terminated.
Lexicographical order is the usual dictionary order. For example:
ape < app < apple < bat
If one string is a prefix of another string, the shorter string is smaller. For example:
app < apple
The judge's main.c reads the input and calls your functions.
The first line contains one integer Q, the number of operations.
Each of the next Q lines contains one operation in one of the following formats:
1 s
2 s
3 p
4
5
The meaning of each operation is:
1 s: call insert_string(root, s).2 s: call delete_string(root, s).3 p: call count_prefix(root, p) and print the returned value.4: call get_min_string(root, ans) and print ans.5: call get_max_string(root, ans) and print ans.
1 <= Q <= 200000
1 <= |s|, |p| <= 100
The total length of all inserted strings and queried prefixes is at most 5 * 10^6.
a to z.1 s and prefixes in operations 3 p. Strings in delete operations 2 s are not counted again.2 s, at least one occurrence of s currently exists.4 or 5, the multiset is not empty.The output is produced by the judge's main.c according to the return values or answer strings produced by your functions.
For each operation 3 p, output one integer: the return value of count_prefix(p).
For each operation 4, output one string: the string written by get_min_string(ans).
For each operation 5, output one string: the string written by get_max_string(ans).
Each answer is printed on its own line.