#P4892. [Tjoi2017]dna

    ID: 4004 传统题 1000ms 256MiB 尝试: 867 已通过: 200 难度: 6 上传者: 标签>难度分类提高字符串后缀数组排序与序列处理倍增计数排序Kasai 算法LCP+RMQ数据结构ST 表CF2100

[Tjoi2017]dna

[TJOI2017] DNA

题目描述

加里敦大学的研究人员发现,基因序列 SS 会让人表现出喜欢吃藕的性状。替换 SS 中至多三个位置的碱基后,仍可能表现出相同的性状。

给定一条 DNA 序列 S0S_0 和基因序列 SS,统计 S0S_0 中有多少个与 SS 等长的连续子串,在替换至多三个碱基后可以变成 SS。起点不同的子串分别计数。

输入格式

第一行有一个整数 TT,表示有几组数据。

每组数据第一行一个长度不超过 10510^5 的碱基序列 S0S_0。

每组数据第二行一个长度不超过 10510^5 的吃藕基因序列 SS。

输出格式

共 TT 行,第 ii 行表示第 ii 组数据中,在 S0S_0 中有多少个与 SS 等长的连续子串可能是表现吃藕性状的碱基序列。

样例 #1

样例输入 #1

1
ATCGCCCTA
CTTCA

样例输出 #1

2

提示

对于 20%20\% 的数据,S0,SS_0,S 的长度不超过 10410^4。

对于 100%100\% 的数据,S0,SS_0,S 的长度不超过 10510^5,0<T≤100\lt T\leq 10。

碱基序列由 A、T、C、G 四种字符组成。