问题 25314 --机密谍报

25314: 机密谍报

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 23
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][68kb]

题目描述

HY 非常喜欢和GJQ 闲聊,而其他人等都还奋斗在OI 的道路上,为了不打扰同学,他们交流统一用密文,交流信息的明文是由0 1 组成的非空序列,而密文是由01 和若干个密码字母组成,每个密码字母代表不同的01 串,例如,密文011a0bf00a01。密码破译的关键是确定每个密码的含义。

经过长期统计分析,现在知道了每个密码的固定长度,如今,蛋疼的同学们又截获了它们俩的两段密文S1 S2 ,并且知道S1 = S2 ,即两段密文代表相同的明文。你的任务是帮助同学们对给定的两段密文进行分析,看一看有多少种可能的明文。

输入

1 行:S1 (1 段密文)

2 行:S2 (2 段密文)

3 行:N (密码总数,N 26)

4-N+3 行:字母i 长度i (密码用小写英文字母表示,密码长度≤ 100)

输出

M(表示有M 种可能的明文)

样例输入

100ad1
cc1
4
a 2
d 3
c 4
b 50

样例输出

2

提示


数据范围



明文的长度≤10000



保证不用高精度



 



Hint



对于本题,如果在并查集中存在x 个集合,那么可能的方案数便是2x



解释一下样例:



由输入可知,a 的长度为2d 的长度为3c 的长度为4b 的长度为50,那么我们便可以将100ad1



cc1 展开成为下面的内容



1 0 0 a1 a2 d1 d2 d3 1



c1 c2 c3 c4 c1 c2 c3 c4 1



那么,在并查集操作后,将会有三个集合出现



1 c1 a2



0 c2 d1 c3 d2



d3 c4 a1


因为10是确定的,所以不确定的只有一个集合,那么答案便是21

来源

[提交][状态]