4511: 「2018 集训队互测 Day 5」Fim4
内存限制：1024 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
黎瑟最近在机器遗忘平台 IQ-- 上租了一台服务器来训练她的梯度上升算法，服务器上存着很大的数据集。由于这些数据集里大部分数据都有很大的相似性，所以这些数据都以一种压缩比很高的方式压缩了起来。
形式化地说，压缩算法会存储一个包含 $n$ 个字符串的字典 $s$，而数据是用一个序列 $a$ 表示的，数据解压后的内容为 $s_{a_1}+s_{a_2}+\ldots+s_{a_m}$。
黎瑟本地硬盘的空间并不富裕，网络条件也不好，因此她只能不断向服务器发送请求，每次询问一个字符串 $qs_i$ 在数据中的出现次数。
但数据解压后的长度实在太大，普通的朴素算法无法工作，为了让她顺利的把实验数据给你写论文，帮她实现这个算法吧。
下面形式化地给出题意：给定 $n$ 个字符串 $s_i$ 和 $m$ 个 $1 \sim n$ 之间的整数 $a_i$，令母串为 $s_{a_1}+s_{a_2}+\ldots+s_{a_m}$，回答 $q$ 次询问，每次给出一个字符串 $qs_i$，询问这个串在母串中的出现次数。请注意 $s_i$ 和 $qs_i$ **都只由字母 `a,b` 组成。**
输入
从标准输入读入数据。
输入第一行包含三个正整数 $n,m,q$，保证 $1\le n,m,q\le 5\times 10^4$。
接下来 $n$ 行，每行一个字符串，表示 $s_i$。
接下来一行 $m$ 个正整数，表示 $a_i$。保证 $\forall 1\leq i\leq m,1\le a_i\le n$。
接下来 $q$ 行，每行一个字符串，表示 $qs_i$。
保证读入的所有字符串都只由字符 `a,b` 组成。
保证 $\sum_{1\leq i\leq n} |s_i|,\sum_{1\leq i\leq q} |qs_i| \le 10^5$。
输出
输出到标准输出。
输出 $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提示
数据范围：本题使用捆绑测试。每个子任务有若干个测试点，分为 $4$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。 $1\le n,m,q\le 5\times 10^4$。 $\sum_{1\leq i\leq n} |s_i|,\sum_{1\leq i\leq q} |qs_i| \le 10^5$。 | 子任务 | 分值 | 特殊性质 | | - | - | - | | 1 | 20| $ \sum_{1\leq i\leq m} \text{len}\left (s_{a_i}\right ) \le 10^6 $ | | 2 | 20 | $ \max \{ \text{len}\left( qs_{i}\right ) \} \le \min \{ \text{len} \left (s_i \right ) \} $ | | 3 | 30 | $ \max \{ \text{len} \left ( qs_{i}\right ) \} \le 200$ | | 4 |30 | 无 |