OI题库

【问题描述】

    信息的明文是由0利1组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由0、1和若干个密码字母组成，每个密码字母代表不同的01串，例如，密文=011a0bf00a01。密码破译的关键是确定每个密码的含义。

    经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文S1和S2，并且知道S1=S2，即两段密文代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。

【输入文件】

第1行： S1 (第1段密文)
第2行： S2 (第2段密文)
第3行： N (密码总数， N<=26)
第4—N+3行： 字母i 长度i (密码用小写英文字母表示， 密码长度<=100)
 

【输出文件】

M（表示有M种可能的明文）
 

【输入输出样例】

encrypt.in

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

encrypt.out

2

【约束条件】

明文的长度<=10000 　

注意：

如果两个密文出现矛盾情况，则输出0。