【CF528D】Fuzzy Search

Source and Judge

CF528D

Record

2h

Analysis

请先思考后再展开

忘记round了,结果本机还对了……调了很久

这道题还是有点妙的
注意到字符集很小,可以逐种字母处理
s1是母串,s2是模式串
发现这种对齐,然后往后推,然后匹配这种东西,把串反过来,和卷积很像
设 $A_i=s2[i]==c,B_i=s1[n-i+1]附近是否含有c$
那么Ci就表示从i开始倒着对齐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const double PI=acos(-1);
const int MAX_N=8*210000;
struct Cp
{
double a,b;
Cp(double c=0,double d=0) {a=c,b=d;}
Cp operator + (Cp t) {return Cp(a+t.a,b+t.b);}
Cp operator - (Cp t) {return Cp(a-t.a,b-t.b);}
Cp operator * (Cp t) {return Cp(a*t.a-b*t.b,a*t.b+b*t.a);}
};
int R[MAX_N];
struct Fft
{
Cp w[MAX_N];
void getw(int n,int f)
{
for(int i=0;i<n;i++) w[i]=Cp(cos(PI*2*f*i/n),sin(PI*2*f*i/n));
}
void solve(Cp *a,int n,int f)
{
for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int ln=1;ln<=n/2;ln<<=1)//合并前
{
getw(ln*2,f);
for(int st=0;st<n;st+=2*ln)
for(int k=0;k<ln;k++)
{
Cp x=a[st+k],y=w[k]*a[st+ln+k];
a[st+k]=x+y;a[st+ln+k]=x-y;
}
}
}
}fft;
void FFT(Cp *a,Cp *b,Cp *c,int ln)
{
fft.solve(a,ln,1);fft.solve(b,ln,1);
for(int i=0;i<ln;i++) c[i]=a[i]*b[i];
fft.solve(c,ln,-1);for(int i=0;i<ln;i++) c[i].a/=ln;
}
int ln1,ln2,k,ln;
char s1[MAX_N],s2[MAX_N];
Cp A[MAX_N],B[MAX_N],C[MAX_N];
int ans[MAX_N];
int tmp[2][MAX_N];
void solve(char c)
{
for(int i=0;i<ln;i++) A[i]=Cp(),B[i]=Cp();
for(int i=0;i<ln2;i++) A[i]=Cp(s2[i]==c,0);
memset(tmp,0,sizeof tmp);
tmp[0][0]=(s1[0]==c)?0:INF;for(int i=1;i<ln1;i++) tmp[0][i]=(s1[i]==c)?0:(tmp[0][i-1]+1);
tmp[1][ln1-1]=(s1[ln1-1]==c)?0:INF;for(int i=ln1-2;i>=0;i--) tmp[1][i]=(s1[i]==c)?0:(tmp[1][i+1]+1);
for(int i=0;i<ln1;i++) B[i]=Cp(min(tmp[0][ln1-1-i],tmp[1][ln1-1-i])<=k,0);
FFT(A,B,C,ln);
for(int i=0;i<ln1;i++) ans[i]+=round(C[ln1-1-i].a);
}
void main()
{
scanf("%d%d%d%s%s",&ln1,&ln2,&k,s1,s2);
ln=1;int lg=0;while(ln<(ln1-1+ln2-1)+1) ln<<=1,lg++;
R[0]=0;for(int i=1;i<ln;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(lg-1));
memset(ans,0,sizeof ans);
solve('A');solve('C');solve('G');solve('T');
int cnt=0;for(int i=0;i<ln1;i++) cnt+=(ans[i]==ln2);
printf("%d",cnt);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e5f5.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%