問題一覧 > 通常問題

No.3667 Prefix Count Queries

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : Rino-program
お気に入りにしたユーザー ProblemId : 13862 / 自分の提出
問題文最終更新日: 2026-08-31 20:49:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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 a changes $S$ to a.
  • The $2$nd query 1 p changes $S$ to ap.
  • For the $3$rd query 3, the strings that have ap as a prefix are apple, api, application, which is $3$ strings, so print $3$.
  • The $4$th query 1 p changes $S$ to app.
  • For the $5$th query 3, the strings that have app as a prefix are apple, application, which is $2$ strings, so print $2$.
  • The $6$th query 2 deletes the last character, and $S$ returns to ap.
  • The $7$th query 1 i changes $S$ to api.
  • For the $8$th query 3, the only string that has api as a prefix is api, 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 has co as 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 are aaa, 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 are aa, 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 is z, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。