题目描述
黎瑟最近在机器遗忘平台 IQ-- 上租了一台服务器来训练她的梯度上升算法,服务器上存着很大的数据集。由于这些数据集里大部分数据都有很大的相似性,所以这些数据都以一种压缩比很高的方式压缩了起来。
形式化地说,压缩算法会存储一个包含 n 个字符串的字典 s,而数据是用一个序列 a 表示的,数据解压后的内容为 sa1+sa2+…+sam。
黎瑟本地硬盘的空间并不富裕,网络条件也不好,因此她只能不断向服务器发送请求,每次询问一个字符串 qsi 在数据中的出现次数。
但数据解压后的长度实在太大,普通的朴素算法无法工作,为了让她顺利的把实验数据给你写论文,帮她实现这个算法吧。
下面形式化地给出题意:给定 n 个字符串 si 和 m 个 1∼n 之间的整数 ai,令母串为 sa1+sa2+…+sam,回答 q 次询问,每次给出一个字符串 qsi,询问这个串在母串中的出现次数。请注意 si 和 qsi 都只由字母 a,b
组成。
输入格式
从标准输入读入数据。
输入第一行包含三个正整数 n,m,q,保证 1≤n,m,q≤5×104。
接下来 n 行,每行一个字符串,表示 si。
接下来一行 m 个正整数,表示 ai。保证 ∀1≤i≤m,1≤ai≤n。
接下来 q 行,每行一个字符串,表示 qsi。
保证读入的所有字符串都只由字符 a,b
组成。
保证 ∑1≤i≤n∣si∣,∑1≤i≤q∣qsi∣≤105。
输出格式
输出到标准输出。
输出 q 行,每行一个整数,表示每个询问的答案。
样例
10 5 10
b
aa
b
bbb
aaa
ba
ba
bb
ba
a
6 5 5 1 5
aba
bbabbabba
bb
aabbbaabb
bbbbbbbbb
bbbbaab
babbbba
aaaaaba
b
baaaaa
1
0
0
0
0
0
0
1
2
1
见附加文件中的 2.in/out
。
数据范围与提示
本题使用捆绑测试。每个子任务有若干个测试点,分为 4 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
1≤n,m,q≤5×104。
∑1≤i≤n∣si∣,∑1≤i≤q∣qsi∣≤105。
子任务 |
分值 |
特殊性质 |
1 |
20 |
∑1≤i≤mlen(sai)≤106 |
2 |
max{len(qsi)}≤min{len(si)} |
3 |
30 |
max{len(qsi)}≤200 |
4 |
无 |