P3763 [TJOI2017] DNA

加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 $S$,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$，任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S_0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S_0$ 上，有多少个连续子串可能是该基因，即有多少个 $S_0$ 的连续子串修改小于等于三个字母能够变成 $S$。

无

无

对于 $20\%$ 的数据，$S_0,S$ 的长度不超过 $10^4$。 对于 $100\%$ 的数据，$S_0,S$ 的长度不超过 $10^5$，$0\lt T\leq 10$。 注：DNA 碱基序列只有 ATCG 四种字符。