Trie (Prefix Count) - Classic Problems | Repovive

CLS33. Trie (Prefix Count)

2s256 MB

Given $n$ operations on a Trie (prefix tree):

For each query, output the answer on a separate line.

\begin{array}{l} n \\ op_1 \\ op_2 \\ \vdots \\ op_n \end{array}

op_j \in \left\{ \begin{array}{ll} \texttt{+} \quad word \\ \texttt{?} \quad prefix \end{array} \right.

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\texttt{?} \text{ queries}\}

Input

7
+ apple
+ app
+ application
? app
+ banana
? ban
? ap

Explanation

For this input, the required output is 3 1 3.

Output

3
1
3

Input

5
? hello
+ hello
? hello
? hell
? helloworld

Explanation

For this input, the required output is 0 1 1 0.

Output

Input

9
+ a
+ ab
+ abc
+ abcd
? a
? ab
? abc
? abcd
? abcde

Explanation

For this input, the required output is 4 3 2 1 0.

Output

Given $n$ operations on a Trie (prefix tree):

For each query, output the answer on a separate line.

\begin{array}{l} n \\ op_1 \\ op_2 \\ \vdots \\ op_n \end{array}

op_j \in \left\{ \begin{array}{ll} \texttt{+} \quad word \\ \texttt{?} \quad prefix \end{array} \right.

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\texttt{?} \text{ queries}\}