BZPRO
#4892. [Tjoi2017]dna
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列S,有这个序列的碱基序列就会表现出喜欢吃藕的
性状，但是研究人员发现对碱基序列S,任意修改其中不超过3个碱基，依然能够表现出吃藕的性状。现在研究人员
想知道这个基因在DNA链S0上的位置。所以你需要统计在一个表现出吃藕性状的人的DNA序列S0上，有多少个连续子
串可能是该基因，即有多少个S0的连续子串修改小于等于三个字母能够变成S。
输入格式
第一行有一个数T,表示有几组数据 每组数据第一行一个长度不超过10^5的碱基序列S0
每组数据第二行一个长度不超过10^5的吃藕基因序列S
输出格式
共T行，第i行表示第i组数据中，在S0中有多少个与S等长的连续子串可能是表现吃藕性状的碱基序列
样例
样例输入
1
ATCGCCCTA
CTTCA
样例输出
2
数据范围与提示
BZPRO