F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5337. -- [TJOI2018]str

5337: [TJOI2018]str

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 69  Solved: 53
[Submit][Status][Discuss]

Description

小豆参加了生物实验室。在实验室里,他主要研究蛋臼质。他现在研究的蛋臼质是由k个氨基酸按一定顺序构成的
。每一个氨基酸都可能有a种碱基序  列si_j 构成。现在小豆有一个碱基串s,小豆想知道在这个碱基上都多少中
不同的组合方式可能得到这个蛋白质。即求由k段字符串有序合并成的字符串s1,有多少种不同方式能够匹配字符串
s,其中k段字符串的选法不同,或者与s匹配上  的位置不同认为是不同的方式。

Input

第一行一个数,表示这个蛋臼质由k个氨基酸。
第二行一个字符串s,表示小豆现在有的碱基串。
第三行开始接下来k行表示第i个氨基酸可能的碱基序列,对于第i个氨基酸,ai表示这个氨基酸可能的碱基序列种数,
接下来ai个字符串表示这ai 种可能的碱基序列,用空格隔开。
1 ≤ k ≤ 100, |s| ≤ 10000,ai ≤ 10

Output

输出一个数目标是不同的方案数
(不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式)

Sample Input

2
ABC
2 A AB
2 C BC

Sample Output

2
提示
第一个选A第二个选C,得到AC能够与ABC产生0中匹配方式
第一个选A第二个选BC,得到ABC能够与ABC产生1中匹配方式
第一个选AB第二个选C,得到ABC能够与ABC产生1中匹配方式
第一个选AB第二个选BC,得到ABBC能够与ABC产生0中匹配方式
所以一共2种

HINT

Source

[Submit][Status][Discuss]

HOME Back