#P4892. [Tjoi2017]dna
[Tjoi2017]dna
[TJOI2017] DNA
题目描述
加里敦大学的研究人员发现,基因序列 会让人表现出喜欢吃藕的性状。替换 中至多三个位置的碱基后,仍可能表现出相同的性状。
给定一条 DNA 序列 和基因序列 ,统计 中有多少个与 等长的连续子串,在替换至多三个碱基后可以变成 。起点不同的子串分别计数。
输入格式
第一行有一个整数 ,表示有几组数据。
每组数据第一行一个长度不超过 的碱基序列 。
每组数据第二行一个长度不超过 的吃藕基因序列 。
输出格式
共 行,第 行表示第 组数据中,在 中有多少个与 等长的连续子串可能是表现吃藕性状的碱基序列。
样例 #1
样例输入 #1
1
ATCGCCCTA
CTTCA
样例输出 #1
2
提示
对于 的数据, 的长度不超过 。
对于 的数据, 的长度不超过 ,。
碱基序列由 A、T、C、G 四种字符组成。