TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

79.7% (157/197)

Submission's AC Ratio

21.8% (522/2390)

Description

給你一個字串 $T$,以及很多字串 $P$。
對於每個 $P$ 請輸出 $P$ 在 $T$ 中出現過幾次。

Input Format

第一行有個數字代表有幾組測資。
每組測資的第一行是字串 $T$,
第二行有個數字 $Q$ 代表有幾個詢問,
接下來的 $Q$ 行每行都有一個字串 $P$。
$T$、$P$ 都是由小寫字母所組成,長度不會超過 $10000$。

Output Format

對於每個詢問輸出 $P$ 在 $T$ 中出現過幾次。

Sample Input

2
abcdefefef
3
bcd
ef
efef
ccodegeass
2
akira
cc

Sample Output

1
3
2
0
1

Hints

2020/10/24 補充測資範圍
測資筆數 $\leq 10$
$Q \leq 50000$
對於單組測資,$P$ 的總長度不會超過 $3.5\times 10^ 5$

Problem Source

原TIOJ1306 / [TIOJ] IOI2008 暖身賽 2(prob F)。Problem Setter:akira。

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12