谁帮帮我 实在做不出来了
超级病毒时间限制:1000 ms | 内存限制:65536 KB
描述
在ACM训练基地最引人注目的一台计算机是一台具有高度人工智能的超级生物计算机。和其他所有计算机不同,这台计算机拥有和人类一样的DNA结构。由于具有高度的人工智能,各位训练队员们都早已把它当成是训练队里不可缺少的一员。
有一天,它们发现这台计算机生病了……
生病以后,这台计算机变得很虚弱,不和我们打招呼了,也不能帮我们想算法题了。队员们都很难过,他们都想帮帮这位好朋友。
经过仔细的检查,它们发现这台计算机感染了一种病毒。和医学中的病毒一样,这种超级病毒侵入计算机运算单元内的细胞,将其感染。于是,正常细胞中的DNA被病毒更改为新的序列。导致细胞机能的变异。
经过仔细比对,训练队员们已经找到了可疑的病毒特征序列,即,如果细胞的DNA序列中包含这种序列,那么该细胞就很可能被感染。
例如,病毒特征代码为ATAA,则如果DNA序列中如果有ATCATAATCATAC这样一段,则细胞就很可能受到感染。
现在,队员们将为生病计算机进行彻底的检查,他们将给出计算机完整的DNA序列(和生物学中的DNA一样,计算机的DNA序列也可以表示为字母A,T,C,G组成的序列),你的任务是,判定该DNA序列中出现过几次病毒特征序列。
注意:其中病毒特征序列在待测DNA序列中重叠出现必须按多次计算。
例如: AATTAATTAA在AATTAATTAATTAA中出现两次。
输入
输入包括多组测试数据,第一行有一个正整数N表示数据数量。
以下为N组测试数据。
每组测试数据由两行,每一行都是由字母A、T、C、G组成的字符串。第一行为病毒特征代码(长度不超过10000个字符)。第二行为待测DNA序列,此序列长度较长(长度不超过1000000个字符)。
输出
对于每一组测试数据,输出一个整数表示答案,为在待测DNA序列中出现病毒特征代码的次数。
样例输入
1
AATTAATTAA
AATTAATTAATTAA
样例输出
2
代码写好的 自己去测试 http://www.
过的发消息 老杨谢过