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

第一行有一个数T，表示有几组数据

每组数据第一行一个长度不超过10⁵的碱基序列S₀

每组数据第二行一个长度不超过10⁵的吃藕基因序列S

共T行，第i行表示第i组数据中，在S ⁰中有多少个与S等长的连续子串可能 是表现吃藕性状的碱基序列

对于20%的数据，S₀，S的长度不超过10⁴

对于100%的数据，S₀，S的长度不超过10⁵

对于所有数据0 < T ≤ 10

TJOI2017 NOIP TJOI2017day2 高级