問題一覧 > 通常問題

No.3667 Prefix Count Queries

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : Rino-program
お気に入りにしたユーザー ProblemId : 13862 / 自分の提出
問題文最終更新日: 2026-08-31 20:49:02

注意

この問題はX/BlueSky/Discordにて公開した事のある問題です。

問題文

$N$ 個の英小文字列 $A_1, A_2, \dots, A_N$ が与えられます。

また、現在空文字列である文字列 $S$ があります。

以下の $Q$ 個のクエリを与えられた順に処理してください。

  • 1 x: 文字列 $S$ の末尾に英小文字 $x$ を追加する。
  • 2: 文字列 $S$ の末尾の文字を $1$ 文字削除する。
  • 3: $A_1, \dots, A_N$ のうち、現在の $S$ を接頭辞として持つものの個数を出力する。

$S$ が空の時に $N$ 個の文字列全てが $S$ を接頭辞として持つものとなることに注意してください。

制約

  • $1 \le N, Q \le 2 \times 10^5$
  • $A_i$ は英小文字からなる長さ $1$ 以上の文字列
  • すべての $A_i$ の長さの合計は $2 \times 10^5$ 以下
  • クエリ $1$ の $x$ は $1$ 文字の英小文字
  • クエリ $2$ のとき、$S$ は空ではない
  • クエリ $3$ は各テストケースに $1$ つ以上存在する
  • $N$, $Q$ は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$
$A_2$
$\vdots$
$A_N$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

各 $\text{query}_i$ は以下のいずれかの形式である。

1 x

2

3

出力

クエリ $3$ の数を $k$ としたとき、$k$ 行出力してください。
$i$ 行目には、$i$ 番目のクエリ $3$ に対する答え（現在の $S$ を接頭辞として持つ文字列の個数）を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
apple
api
application
8
1 a
1 p
3
1 p
3
2
1 i
3
出力
3
2
1

最初、$S$ は空文字列です。

  • $1$ つ目のクエリ 1 a で、$S$ は a になります。
  • $2$ つ目のクエリ 1 p で、$S$ は ap になります。
  • $3$ つ目のクエリ 3 で、ap を接頭辞に持つ文字列は apple, api, application の $3$ つなので、$3$ を出力します。
  • $4$ つ目のクエリ 1 p で、$S$ は app になります。
  • $5$ つ目のクエリ 3 で、app を接頭辞に持つ文字列は apple, application の $2$ つなので、$2$ を出力します。
  • $6$ つ目のクエリ 2 で、末尾の文字が削除され $S$ は ap に戻ります。
  • $7$ つ目のクエリ 1 i で、$S$ は api になります。
  • $8$ つ目のクエリ 3 で、api を接頭辞に持つ文字列は api の $1$ つのみなので、$1$ を出力します。
サンプル2
入力
2
cat
dog
5
3
1 c
1 o
3
2
出力
2
0
  • $1$ つ目のクエリ 3 では、$S$ は空文字列です。すべての文字列が空文字列を接頭辞として持つため、$N$ と同じ $2$ を出力します。
  • その後、$S$ は c $\to$ co と変化します。
  • $4$ つ目のクエリ 3 では、co を接頭辞に持つ文字列は存在しないため、$0$ を出力します。
サンプル3
入力
3
abc
abc
a
4
1 a
3
1 b
3
出力
3
2

$A$ には同じ文字列が複数含まれることもあります。
$S$ が ab のとき、abc（$1$ つ目）と abc（$2$ つ目）が条件を満たします。

サンプル4
入力
4
a
aa
aaa
aaaa
7
1 a
1 a
1 a
3
2
3
2
出力
2
3
  • $4$ つ目のクエリの時点で $S$ は aaa となっており、これを接頭辞に持つのは aaa, aaaa の $2$ つです。
  • $6$ つ目のクエリの時点で $S$ は aa となっており、これを接頭辞に持つのは aa, aaa, aaaa の $3$ つです。
サンプル5
入力
1
z
6
1 z
3
1 z
3
2
3
出力
1
0
1
  • $S$ が z のとき、接頭辞として持つのは z の $1$ つです。
  • $S$ が zz のとき、接頭辞として持つ文字列は存在しないため $0$ を出力します。$S$ の長さが $A_i$ の長さを超えることもあります。
  • その後、末尾が削除されて $S$ が再び z に戻り、答えは $1$ になります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。