当前没有测试数据。

2.字符串计数

题目描述

给你一个文本串$S$和$n$个模式串$T_1$~$T_n$，请你分别求出每个模式串$T_i$在$S$中出现的次数。

输入格式

第一行包含一个正整数$n$表示模式串的个数。

接下来$n$行，第$i$行包含一个由小写英文字母构成的字符串$T_i$。

最后一行包含一个由小写英文字母构成的字符串$S$。

数据不保证任意两个模式串不相同。

输出格式

输出包含$n$行，其中第$i$行包含一个非负整数表示$T_i$在$S$中出现的次数。

数据范围与提示

对于$100\%$的数据，$1 \leq n \leq 2 \times 10^{5}$，$\sum_{i=1}^{n} \text{length}(T_i) \leq 2 \times 10^{5}$，$\text{length}(S) \leq 2 \times 10^{6}$。

样例

5
a
bb
aa
abaa
abaaa
abaaabaa

6
0
3
2
1