【纪中集训2019.3.13】碱基配对
题目：
描述
给出长度为\(n\)的字符串\(A\)和长度为\(m\)的字符串\(B\)，仅由字符\(Z,P,S,B\)构成；
定义B在A中的\(p\)位置匹配为：对于任意的\(0 \lt j \lt m\) , 在\(A_{p+j - k}到A_{p+j+k}\) 间存在等于\(B_{j}\)的字符；
求\(B\)在\(A\)中所有的匹配位置；
范围
$1 \le n,m \le 2e5 , 0 \le k \le n $
题解：
可以预处理出一个字符的有效区间\([i-k,i+k]\)
然后依次考虑每一个字符然后取并集
然后对于每一个字符，\(FFT\) 找出不合法的位置
#include
#define ld double
using namespace std;
const int N=800010;
const ld pi=acos(-1);
int n,m,k,rev[N],len,L,ok[N],cnt[N];
char S[N],T[N];
char gc(){static char*p1,*p2,s[1000000];if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);return(p1==p2)?EOF:*p1++;
}
int rd(){int x=0;char c=gc();while(c<'0'||c>'9')c=gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();return x;
}
int gt(char *s){char c=gc(),*p=s;while(!isalpha(c))c=gc();while(isalpha(c))*p++=c,c=gc();return p-s;
}
struct C{ld x,y;C(ld _x=0,ld _y=0):x(_x),y(_y){};C operator +(const C&A)const{return C(x+A.x,y+A.y);}C operator -(const C&A)const{return C(x-A.x,y-A.y);}C operator *(const C&A)const{return C(x*A.x-y*A.y,x*A.y+y*A.x);}C operator /(const ld&A)const{return C(x/A,y/A);}
}A[N],B[N];
void fft(C*a,int f){for(int i=1;i>1]>>1)|((i&1)<<(L-1));}if(n 转载于:https://www.cnblogs.com/Paul-Guderian/p/10532904.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！