51NOD 1565：模糊搜索—

http://www.51nod.com/onlineJudge/questionCode.html#problemId=1565&noticeId=445588

有两个基因串S和T，他们只包含AGCT四种字符。现在你要找出T在S中出现了几次。

有一个门限值k≥0。T在S的第i(1≤i≤|S|-|T|+1)个位置中出现的条件如下：把T的开头和S的第i个字符对齐，然后T中的每一个字符能够在S中找到一样的，且位置偏差不超过k的，那么就认为T在S的第i个位置中出现。也就是说对于所有的 j (1≤j≤|T|)，存在一个 p (1≤p≤|S|)，使得|(i+j-1)-p|≤k 和[p]=T[j]都成立。

例如，根据这样的定义"ACAT"出现在"AGCAATTCAT"的第2，3和6的位置。

如果k=0，那么这个就是经典的字符串匹配问题。

现在给定门限和两个基因串S，T，求出T在S中出现的次数。

参考：https://www.cnblogs.com/ivorysi/p/9185805.html

首先用差分/线段树处理出每个位置是否能够匹配A/T/C/G，令$a[i][j]$存之，表示$i$这个字符在$j$这个位置是否能被匹配上。

然后我们处理模式串，令$b[i][j]$表示$i$这个字符在$j$这个位置是否存在。

然后就是套路了：BZOJ4259：残缺的字符串对大部分模糊匹配都是一个套路。

我们将模式串倒置然后末尾补0，令：

$f[k][i]=\sum_{j=0}^i(b[k][j]-a[k][i-j])b[k][j]$，当$f[k][j]==0$时说明我们只看$k$字符时模式串能被以$i$为终点的字符串所匹配上。

（我们后面多乘的那个是为了防止该位置不存在$k$字符所设置的。）

展开得到：

$f[k][i]=\sum_{j=0}^ib[k][j]^2-\sum_{j=0}^ia[k][i-j]b[k][j]$

后者是一个卷积，可以直接FFT，前者的2次方其实也可以直接拿掉（因为$1^2=1,0^2=0$）

显然当所有的字符情况下均满足$f[i]==0$的时候$i$就是一个合法位点了。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef double dl;

const int N=4e5+;

const dl pi=acos(-1.0);

const int INF=;

struct complex{

    dl x,y;

    complex(dl xx=0.0,dl yy=0.0){

    x=xx,y=yy;

    }

    complex operator +(const complex &b)const{

    return complex(x+b.x,y+b.y);

    }

    complex operator -(const complex &b)const{

    return complex(x-b.x,y-b.y);

    }

    complex operator *(const complex &b)const{

    return complex(x*b.x-y*b.y,x*b.y+y*b.x);

    }

};

void FFT(complex a[],int n,int on){

    for(int i=,j=n>>;i<n-;i++){

    if(i<j)swap(a[i],a[j]);

    int k=n>>;

    while(j>=k){j-=k;k>>=;}

    if(j<k)j+=k;

    }

    for(int i=;i<=n;i<<=){

    complex res(cos(-*pi*on/i),sin(-*pi*on/i));

    for(int j=;j<n;j+=i){

        complex w(,);

        for(int k=j;k<j+i/;k++){

        complex u=a[k],t=w*a[k+i/];

        a[k]=u+t;a[k+i/]=u-t;

        w=w*res;

        }

    }

    }

    if(on==-)

    for(int i=;i<n;i++)a[i].x/=n;

}

inline int turn(char ch){

    if(ch=='A')return ;

    if(ch=='G')return ;

    if(ch=='C')return ;

    return ;

}

char s1[N],s2[N];

int n,m,k,t[N][];

int a[][N],b[][N],ans[N];

complex A[N],B[N];

bool can[N];

int main(){

    scanf("%d%d%d",&n,&m,&k);

    scanf("%s%s",s1,s2);

    for(int i=;i<n;i++){

    int w=turn(s1[i]);

    int l=max(,i-k),r=min(n-,i+k);

    t[l][w]++;t[r+][w]--;

    }

    for(int i=;i<n;i++)

    for(int j=;j<;j++){

        if(i)t[i][j]+=t[i-][j];

        if(t[i][j]>)a[j][i]=;

    }

    for(int i=;i<m;i++)b[turn(s2[m-i-])][i]=;

    int len=;

    while(len<n)len<<=;

    for(int i=;i<;i++){

    for(int j=;j<n;j++)

        ans[j]=(j?ans[j-]:)+b[i][j];

    for(int j=;j<len;j++){

        A[j]=complex(a[i][j],);

        B[j]=complex(b[i][j],);

    }

    FFT(A,len,);FFT(B,len,);

    for(int j=;j<len;j++)A[j]=A[j]*B[j];

    FFT(A,len,-);

    for(int j=;j<n;j++)ans[j]-=(int)(A[j].x+0.5);

    for(int j=;j<n;j++)if(ans[j])can[j]=;

    }

    int cnt=;

    for(int i=m-;i<n;i++)if(!can[i])cnt++;

    printf("%d\n",cnt);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

51NOD 1565：模糊搜索——题解

最新文章

热门文章