#1766. Fim4
Fim4
Fim4
题目描述
标题: Fim4 - Problem - QOJ.ac
#10375. Fim4
黎瑟最近在机器遗忘平台 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 行,每行一个整数,表示每个询问的答案。
样例数据
样例 1 输入
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 输出
1
0
0
0
0
0
0
1
2
1
样例 2
见下发文件
子任务
本题使用捆绑测试。每个子任务有若干个测试点,分为 4 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
1≤n,m,q≤5×104。
∑1≤i≤n|si|,∑1≤i≤q|qsi|≤105。
子任务 分值 特殊性质 1 20 ∑1≤i≤mlen(sai)≤106 2 20 max{len(qsi)}≤min{len(si)} 3 30 max{len(qsi)}≤200 4 30 无
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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