当前位置：首页 > news >正文

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

news 来源：原创 2024/5/4 20:48:36

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+5;
const dl pi=acos(-1.0);
const int INF=4;
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=1,j=n>>1;i<n-1;i++){
    if(i<j)swap(a[i],a[j]);
    int k=n>>1;
    while(j>=k){j-=k;k>>=1;}
    if(j<k)j+=k;
    }
    for(int i=2;i<=n;i<<=1){
    complex res(cos(-2*pi*on/i),sin(-2*pi*on/i));
    for(int j=0;j<n;j+=i){
        complex w(1,0);
        for(int k=j;k<j+i/2;k++){
        complex u=a[k],t=w*a[k+i/2];
        a[k]=u+t;a[k+i/2]=u-t;
        w=w*res;
        }
    }
    }
    if(on==-1)
    for(int i=0;i<n;i++)a[i].x/=n;
}
inline int turn(char ch){
    if(ch=='A')return 0;
    if(ch=='G')return 1;
    if(ch=='C')return 2;
    return 3;
}
char s1[N],s2[N];
int n,m,k,t[N][4];
int a[4][N],b[4][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=0;i<n;i++){
    int w=turn(s1[i]);
    int l=max(0,i-k),r=min(n-1,i+k);
    t[l][w]++;t[r+1][w]--;
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<4;j++){
        if(i)t[i][j]+=t[i-1][j];
        if(t[i][j]>0)a[j][i]=1;
    }
    for(int i=0;i<m;i++)b[turn(s2[m-i-1])][i]=1;
    
    int len=1;
    while(len<n)len<<=1;
    for(int i=0;i<4;i++){
    for(int j=0;j<n;j++)
        ans[j]=(j?ans[j-1]:0)+b[i][j];

    for(int j=0;j<len;j++){
        A[j]=complex(a[i][j],0);
        B[j]=complex(b[i][j],0);
    }
    FFT(A,len,1);FFT(B,len,1);
    for(int j=0;j<len;j++)A[j]=A[j]*B[j];
    FFT(A,len,-1);
    for(int j=0;j<n;j++)ans[j]-=(int)(A[j].x+0.5);

    for(int j=0;j<n;j++)if(ans[j])can[j]=1;
    }
    int cnt=0;
    for(int i=m-1;i<n;i++)if(!can[i])cnt++;
    printf("%d\n",cnt);
    return 0;
}