BZPRO

#2764. [JLOI2011]基因补全

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

在生物课中我们学过，碱基组成了DNA（脱氧核糖核酸），他们分别可以用大写字母A,C,T,G表示，其中A总与T配对，C总与G配对。两个碱基序列能相互匹配，当且仅当它们等长，并且任意相同位置的碱基都是能相互配对的。例如ACGTC能且仅能与TGCAG配对。一个相对短的碱基序列能通过往该序列中任意位置补足碱基来与一个相对长的碱基序列配对。补全碱基的位置、数量不同，都将视为不同的补全方案。现在有两串碱基序列S和T，分别有n和m个碱基(n>=m)，问一共有多少种补全方案。
 

输入格式

数据包括三行。
第一行有两个整数n，m，表示碱基序列的长度。
第二行包含n个字符，表示碱基序列S。
第三行包含m个字符，表示碱基序列T。
两个碱基序列的字符种类只有A,C,G,T这4个大写字母。
 

输出格式

 
答案只包含一行，表示补全方案的个数。

样例

样例输入


			
10 3

CTAGTAGAAG

TCC

样例输出


			
4

数据范围与提示

样例解释:


TCC的4种补全方案（括号中字符为补全的碱基）


(GA)TC(AT)C(TTC)


(GA)TC(ATCTT)C


(GA)T(CAT)C(TT)C


(GATCA)TC(TT)C


 


数据范围:


30%数据n<=1000,m<=2


50%数据n<=1000,m<=4


100%数据n<=2000,m<=n


BZPRO Powered by Remmina.
Github Repository