Fuzzy Search
题目描述
题解
由题可知\(1\leq i \leq |S|-|T|+1\)
首先转化下条件\(|i+j-1-p|\leq k, S[p]=T[j]\)
其实就是
对于每个\(T[j](1\leq j \leq |T|)，对应着S[i+j-1]的前后各k个是否存在S[p]=T[j](|i+j-1-p|\leq k)\)
也就是判断
\(\sum_{j=1}^{|T|}[T_j==S_p]\cdot [|i+j-1-p|\leq k] 的和是否=|T|\)
因为只有四个单词，分别讨论，以下以字符A来讨论，其他类似
设\(f(i,A)=\sum_{j=1}^{|T|}[T_j=='A']\cdot[S_p=='A']\cdot[|i+j-1-p|\leq k]\)
只要\(f(i,A)+f(i,G)+f(i,C)+f(i,T)=|T|, i就满足条件\)
但计算\(f(i,A)\)的条件还是比较复杂
首先考虑一个字符A
对于字符串\(S=\{**A***A***A**\} (*表示非A的其他字符)\)
转化为\(S'=\{*AAA*AAA*AAA*\} (假设k=1,只是描述下转化过程)\)
那么\(f(i,A)=\sum_{j=1}^{|T|}[T_j=='A']\cdot[S'_{i+j-1}=='A']\)
考虑把S'翻转下，就会惊奇发现上面式子成了一个卷积形式
\(f(i,A)=\sum_{j=1}^{|T|} [T_j=='A'] \cdot [S'_{|S|-i-j+2}=='A']\)
设多项式
\(T(x)=\sum_{j=1}^{|T|} [T_j=='A']x^j\)
\(S(x)=\sum_{i=1}^{|S|} [S'_{|S|-i+1}]=='A'] x^i\)
\([x^k]T(x)S(x)=\sum_{j=1}^{|T|}[T_j=='A'][S'_{|S|-(k-j)}=='A']\)
\(f(i,A)=[x^{|S|-i+2}]T(x)S(x)\)
以此类推出其他三个字符的结果，最后判断下就行
点击查看代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=2e6+101;
const int MOD=100007;
const int inf=2147483647;
const double pi=acos(-1);
int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
return x*f;
}
typedef complex cd;
int n,m,nn,k,book[maxn],rev[maxn];
char s[maxn],t[maxn];
void get(int bit){
for(int i=0;i<(1<>1]>>1)|((i&1)<<(bit-1));
}
void dft(cd *u,int val){
for(int i=0;i>s>>t;
int len=0;
for(nn=1;nn<=n+m;nn<<=1)len++;get(len);
solve('A');solve('G');solve('C');solve('T');
int ans=0;
for(int i=1;i<=n-m+1;i++){
ll f1=(ll)(f[1][n-i+2].real()/nn+0.5);
ll f2=(ll)(f[2][n-i+2].real()/nn+0.5);
ll f3=(ll)(f[3][n-i+2].real()/nn+0.5);
ll f4=(ll)(f[4][n-i+2].real()/nn+0.5);
if(f1+f2+f3+f4==m)ans++;
}
printf("%d",ans);
return 0;
}