No.3667 Prefix Count Queries
タグ : / 解いたユーザー数 20
作問者 :
Note
This problem has previously been published on X/BlueSky/Discord.
Problem Statement
You are given $N$ strings of lowercase English letters $A_1, A_2, \dots, A_N$.
There is also a string $S$, which is currently empty.
Process the following $Q$ queries in the given order.
1 x: Append the lowercase English letter $x$ to the end of the string $S$.2: Delete $1$ character from the end of the string $S$.3: Print the number of strings among $A_1, \dots, A_N$ that have the current $S$ as a prefix.
Note that when $S$ is empty, all $N$ strings have $S$ as a prefix.
Constraints
- $1 \le N, Q \le 2 \times 10^5$
- $A_i$ is a string of lowercase English letters with length at least $1$
- The total length of all $A_i$ is at most $2 \times 10^5$
- $x$ in query $1$ is $1$ lowercase English letter
- For query $2$, $S$ is not empty
- Each test case contains at least $1$ query $3$
- $N$, $Q$ are integers.
Input
The input is given from standard input in the following format.
$N$
$A_1$
$A_2$
$\vdots$
$A_N$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
Each $\text{query}_i$ is in one of the following formats.
1 x
2
3
Output
Let $k$ be the number of queries $3$. Print $k$ lines.
On the $i$-th line, print the answer to the $i$-th query $3$ (the number of strings that have the current $S$ as a prefix).
Print a newline at the end.
Sample
Sample 1
Input
3 apple api application 8 1 a 1 p 3 1 p 3 2 1 i 3
Output
3 2 1
Initially, $S$ is an empty string.
- The $1$st query
1 achanges $S$ toa. - The $2$nd query
1 pchanges $S$ toap. - For the $3$rd query
3, the strings that haveapas a prefix areapple,api,application, which is $3$ strings, so print $3$. - The $4$th query
1 pchanges $S$ toapp. - For the $5$th query
3, the strings that haveappas a prefix areapple,application, which is $2$ strings, so print $2$. - The $6$th query
2deletes the last character, and $S$ returns toap. - The $7$th query
1 ichanges $S$ toapi. - For the $8$th query
3, the only string that hasapias a prefix isapi, which is $1$ string, so print $1$.
Sample 2
Input
2 cat dog 5 3 1 c 1 o 3 2
Output
2 0
- At the $1$st query
3, $S$ is an empty string. Since all strings have the empty string as a prefix, print $2$, which is equal to $N$. - After that, $S$ changes as
c$\to$co. - For the $4$th query
3, no string hascoas a prefix, so print $0$.
Sample 3
Input
3 abc abc a 4 1 a 3 1 b 3
Output
3 2
$A$ may contain multiple identical strings.
When $S$ is ab, abc (the $1$st one) and abc (the $2$nd one) satisfy the condition.
Sample 4
Input
4 a aa aaa aaaa 7 1 a 1 a 1 a 3 2 3 2
Output
2 3
- At the time of the $4$th query, $S$ is
aaa, and the strings that have it as a prefix areaaa,aaaa, which is $2$ strings. - At the time of the $6$th query, $S$ is
aa, and the strings that have it as a prefix areaa,aaa,aaaa, which is $3$ strings.
Sample 5
Input
1 z 6 1 z 3 1 z 3 2 3
Output
1 0 1
- When $S$ is
z, the only string that has it as a prefix isz, which is $1$ string. - When $S$ is
zz, no string has it as a prefix, so print $0$. The length of $S$ may exceed the length of $A_i$. - After that, the last character is deleted, $S$ returns to
z, and the answer is $1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。