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

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


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

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

Description

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

Tag

二分,Hash

解决思路

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

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101000;
const ull Base=37;
const int inf=2147483647;

int L1,L2;
char str1[maxN],str2[maxN];
ull H1[maxN],H2[maxN];
ull R[maxN];

void InitHash(char *str,ull *H);
ull GetHash(ull *H,int l,int r);

int main()
{
    int T;scanf("%d",&T);
    R[0]=1;
    for (int i=1;i<maxN;i++) R[i]=R[i-1]*Base;
    while (T--)
    {
        scanf("%s",str1+1);scanf("%s",str2+1);
        L1=strlen(str1+1);L2=strlen(str2+1);
        if (L1<L2)
        {
            printf("0\n");
            continue;
        }
        InitHash(str1,H1);InitHash(str2,H2);
        int Ans=0;
        for (int i=1;i+L2-1<=L1;i++)
        {
            int l1=i,l2=1;
            for (int tim=1;tim<=4;tim++)
            {
                int L=l1,R=i+L2-1;
                int pos=l1-1;
                do
                {
                    int mid=(L+R)>>1;int sz=mid-l1+1;
                    if (GetHash(H1,l1,mid)==GetHash(H2,l2,l2+sz-1)){
                        L=mid+1;pos=mid;
                    }
                    else R=mid-1;
                }
                while (L<=R);
                l1=pos+2;l2=pos-i+3;
                if (tim==4) l1--,l2--;
                if (l1>i+L2-1) break;
            }
            if (l1>i+L2-1) Ans++;
        }
        printf("%d\n",Ans);
    }
    return 0;
}

void InitHash(char *str,ull *H)
{
    int len=strlen(str+1);
    H[0]=0;
    for (int i=1;i<=len;i++) H[i]=H[i-1]*Base+str[i];
    return;
}

ull GetHash(ull *H,int l,int r)
{
    return H[r]-H[l-1]*R[r-l+1];
}

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

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


HNCJ OIer