A5801. 「TJOI2017」DNA
编程题
省选/NOI-
知识点
题目描述
加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 $S$,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$，任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S_0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S_0$ 上，有多少个连续子串可能是该基因，即有多少个 $S_0$ 的连续子串修改小于等于三个字母能够变成 $S$。
输入格式
第一行有一个整数 $T$，表示有几组数据。
每组数据第一行一个长度不超过 $10^5$ 的碱基序列 $S_0$。
每组数据第二行一个长度不超过 $10^5$ 的吃藕基因序列 $S$。
每组数据第一行一个长度不超过 $10^5$ 的碱基序列 $S_0$。
每组数据第二行一个长度不超过 $10^5$ 的吃藕基因序列 $S$。
输出格式
共 $T$ 行，第 $i$ 行表示第 $i$ 组数据中，在 $S_0$ 中有多少个与 $S$ 等长的连续子串可能是表现吃藕性状的碱基序列。
输入输出样例
输入 #1
1 ATCGCCCTA CTTCA
输出 #1
2
说明/提示
- 对于 $20\%$ 的数据，$S_0,S$ 的长度不超过 $10^4$。
- 对于 $100\%$ 的数据，$S_0,S$ 的长度不超过 $10^5$，$0\lt T\leq 10$。
注：DNA 碱基序列只有 ATCG 四种字符。
- 对于 $100\%$ 的数据，$S_0,S$ 的长度不超过 $10^5$，$0\lt T\leq 10$。
注：DNA 碱基序列只有 ATCG 四种字符。