[BZOJ4892/Luogu3763][TJOI2017]DNA(二分,Hash)

发布于 2018-05-09  158 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4892/Luogu3763][TJOI2017]DNA(二分,Hash)

Description

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

Tag

二分,Hash

解决思路

枚举起始位置,然后求四遍$lcp$,若四遍以内能够匹配完,则说明能够匹配,否则不行。
求$lcp$有两种方式,一种是后缀数组+$rmp$的方式,另一种是二分+$hash$,这里采用二分+$hash$的方式。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4892/Luogu3763][TJOI2017]DNA(二分,Hash)


HNCJ OIer