3371 - 模式串出现次数
时间限制 : 1 秒
内存限制 : 512 MB
给定一个文本串 S 和 n 个模式串 T1∼n，请你分别求出每个模式串 Ti 在 S 中出现 的次数。
输入
第一行包含一个正整数 n 表示模式串的个数。
接下来 n 行，第 i 行包含一个由小写英文字母构成的非空字符串 Ti。
最后一行包含一个由小写英文字母构成的非空字符串 S。
输出
输出包含 n 行，其中第 i 行包含一个非负整数表示 Ti 在 S 中出现的次数。
样例
输入
5 a bb aa abaa abaaa abaaabaa
输出
6 0 3 2 1
提示
【数据范围】
对于 100% 的数据， 1 ≤ n ≤ 2 × 10^5 ，T1∼n 的长度总和不超过 2 × 10^5 ，S 的 长度不超过 2 × 10^6。