P3763 [TJOI2017]DNA

    • 543通过
    • 1.4K提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 RMQ 后缀数组,SA 哈希,HASH 快速傅里叶变换,DFT,FFT 枚举,暴力 各省省选 2017 天津 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

    第一行有一个数T,表示有几组数据 每组数据第一行一个长度不超过10^5的碱基序列S0

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    1
    ATCGCCCTA
    CTTCA
    输出样例#1: 复制
    2

    说明

    对于20%的数据,S0,S的长度不超过10^4

    对于20%的数据,S0,S的长度不超过10^5,0<T<=10

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。