B - Library Book Search Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は図書館の蔵書検索システムを開発しています。この図書館には N 個の本棚があり、i 番目の本棚（1 \leq i \leq N）には K_i 冊の本が置かれています。i 番目の本棚の j 冊目の本のタイトルを S_{i,j} と表します。タイトルはすべて英小文字のみからなる文字列です。

この検索システムでは、利用者が検索クエリとして文字列を入力すると、そのクエリに関連する本が置かれている本棚を探し出します。利用者は本のタイトルを正確に覚えていないことが多く、タイトルの中から何文字かを（連続していなくてもよいので）順番通りに拾って入力し、検索することがあります。そこで、このシステムでは部分列（subsequence）による検索が採用されています。

ここで、文字列 T が文字列 S の 部分列 であるとは、S から 0 文字以上の文字を取り除いて（残った文字の順序は変えずに）T を得ることができることを言います。例えば、ace は abcde の部分列ですが、aec は abcde の部分列ではありません。

i 番目の本棚がクエリ文字列 T に ヒット するとは、T が S_{i,1}, S_{i,2}, \ldots, S_{i,K_i} のうち少なくとも 1 つの部分列であることを意味します。すなわち、その本棚に少なくとも 1 冊、タイトルが T を部分列として含む本が存在するということです。

Q 個の検索クエリが与えられます。j 番目のクエリの文字列を T_j とします。各クエリについて、クエリ T_j にヒットする本棚の数を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K_i \leq 5000
  • 1 \leq \displaystyle\sum_{i=1}^{N} K_i \leq 5000
  • 各タイトル S_{i,j} の長さは 1 以上 1000 以下である
  • \displaystyle\sum_{i=1}^{N}\sum_{j=1}^{K_i} |S_{i,j}| \leq 10^5
  • 1 \leq Q \leq 200
  • 各クエリ T_j の長さは 1 以上 1000 以下である
  • \displaystyle\sum_{j=1}^{Q} |T_j| \leq 10^5
  • S_{i,j} および T_j は英小文字のみからなる文字列である

ここで |X| は文字列 X の長さを表す。

入力

N
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1}
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2}
\vdots
K_N S_{N,1} S_{N,2} \ldots S_{N,K_N}
Q
T_1
T_2
\vdots
T_Q
  • 1 行目には、本棚の数を表す整数 N が与えられる。
  • 2 行目から N+1 行目まで、i+1 行目（1 \leq i \leq N）には、i 番目の本棚に置かれている本の冊数 K_i と、それぞれの本のタイトル S_{i,1}, S_{i,2}, \ldots, S_{i,K_i} がスペース区切りで与えられる。
  • N+2 行目には、検索クエリの個数を表す整数 Q が与えられる。
  • N+3 行目から N+Q+2 行目まで、j 番目のクエリ（1 \leq j \leq Q）に対応する行には、検索クエリの文字列 T_j が与えられる。

出力

Q 行出力せよ。j 行目（1 \leq j \leq Q）には、クエリ T_j にヒットする本棚の数を出力せよ。

入力例 1

2
2 algorithm data
2 string graph
3
ag
ri
zz

出力例 1

1
2
0

入力例 2

3
1 programming
2 problem process
2 apple application
4
po
pin
pp
rm

出力例 2

3
2
1
2

入力例 3

5
3 binary search tree
2 dynamic programming
1 graph
2 stack queue
3 linked list array
5
ar
ra
i
zzz
ee

出力例 3

2
3
3
0
2

Score : 333 pts

Problem Statement

Takahashi is developing a book search system for a library. The library has N bookshelves, and the i-th bookshelf (1 \leq i \leq N) contains K_i books. The title of the j-th book on the i-th bookshelf is denoted by S_{i,j}. All titles are strings consisting only of lowercase English letters.

In this search system, when a user inputs a string as a search query, the system finds bookshelves that contain books related to the query. Since users often do not remember the exact title of a book, they may pick some characters from the title in order (not necessarily consecutive) and input them as a search. Therefore, this system adopts search by subsequence.

Here, a string T is a subsequence of a string S if T can be obtained by removing 0 or more characters from S (without changing the order of the remaining characters). For example, ace is a subsequence of abcde, but aec is not a subsequence of abcde.

The i-th bookshelf hits a query string T if T is a subsequence of at least one of S_{i,1}, S_{i,2}, \ldots, S_{i,K_i}. In other words, there exists at least one book on that bookshelf whose title contains T as a subsequence.

You are given Q search queries. Let T_j be the string of the j-th query. For each query, find the number of bookshelves that hit the query T_j.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K_i \leq 5000
  • 1 \leq \displaystyle\sum_{i=1}^{N} K_i \leq 5000
  • The length of each title S_{i,j} is between 1 and 1000, inclusive
  • \displaystyle\sum_{i=1}^{N}\sum_{j=1}^{K_i} |S_{i,j}| \leq 10^5
  • 1 \leq Q \leq 200
  • The length of each query T_j is between 1 and 1000, inclusive
  • \displaystyle\sum_{j=1}^{Q} |T_j| \leq 10^5
  • S_{i,j} and T_j are strings consisting only of lowercase English letters

Here, |X| denotes the length of string X.

Input

N
K_1 S_{1,1} S_{1,2} \ldots S_{1,K_1}
K_2 S_{2,1} S_{2,2} \ldots S_{2,K_2}
\vdots
K_N S_{N,1} S_{N,2} \ldots S_{N,K_N}
Q
T_1
T_2
\vdots
T_Q
  • The first line contains an integer N, the number of bookshelves.
  • From the 2nd line to the (N+1)-th line, the (i+1)-th line (1 \leq i \leq N) contains the number of books K_i on the i-th bookshelf, followed by the titles S_{i,1}, S_{i,2}, \ldots, S_{i,K_i}, separated by spaces.
  • The (N+2)-th line contains an integer Q, the number of search queries.
  • From the (N+3)-th line to the (N+Q+2)-th line, the line corresponding to the j-th query (1 \leq j \leq Q) contains the search query string T_j.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the number of bookshelves that hit the query T_j.

Sample Input 1

2
2 algorithm data
2 string graph
3
ag
ri
zz

Sample Output 1

1
2
0

Sample Input 2

3
1 programming
2 problem process
2 apple application
4
po
pin
pp
rm

Sample Output 2

3
2
1
2

Sample Input 3

5
3 binary search tree
2 dynamic programming
1 graph
2 stack queue
3 linked list array
5
ar
ra
i
zzz
ee

Sample Output 3

2
3
3
0
2