BZOJ4259 残缺的字符串(FFT)

题目链接

洛谷

darkbzoj

题意简述

带通配符的单模式串、单文本串匹配。

字符串长度 $3\times10^5$。

简要做法

这题是利用字符串的距离函数来匹配字符串,使用 FFT 优化距离函数的计算。

将通配符的值设为零,定义 $dis(s,t)=\sum(s[i]-t[i])^2s[i]t[i]​$,那么两个等长的字符串匹配当且仅当它们的距离为零。

为了方便卷积,将题目中的 $A$ 串翻转​得到串 $A’​$。

推一波式子:

$\begin{aligned}dis(A,B[i..i+m-1])&=\sum\limits_{j=0}^{m-1}(A’[m-j-1]-B[i+j])^2A’[m-j-1]B[i+j]\\&=\left(\sum\limits_{j=0}^{m-1}A’[m-j-1]B^3[i+j]\right)-2\left(\sum\limits_{j=0}^{m-1}(A’)^2[m-j-1]B^2[i+j]\right)+\left(\sum\limits_{j=0}^{m-1}(A’)^3[m-j-1]B[i+j]\right)\end{aligned}$

设 $f(i)=\sum\limits_{j=0}^{i}A’[i-j]B^3[j]​$(即它们的卷积),将 $A’[m..n-1]​$ 设为 $0​$,那么 $\sum\limits_{j=0}^{m-1}A’[m-j-1]B^3[i+j]=f(i+m-1)​$。

可以类似地计算另外两项,就可以求出所有 $dis(A,B[i..i+m-1])​$,看看哪些等于零就好了。

参考代码

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
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1<<19;
const double PI=acos(-1);

struct cp
{
double re,im;
cp(double _re=0.0,double _im=0.0) { re=_re; im=_im; }
cp operator+(const cp& b) const { return cp(re+b.re,im+b.im); }
cp operator-(const cp& b) const { return cp(re-b.re,im-b.im); }
cp operator*(const cp& b) const { return cp(re*b.re-im*b.im,re*b.im+im*b.re); }
} a[N],a2[N],a3[N],b[N],b2[N],b3[N],c1[N],c2[N],c3[N];

void fft(cp* A,int type);

int n,m,lim,L,r[N];
char s[N],t[N];
vector<int> ans;

int main()
{
int i;

scanf("%d%d%s%s",&m,&n,s,t);

for (i=0;i<n;++i)
{
if (m-i>0&&s[m-i-1]!='*')
{
a[i].re=s[m-i-1]-'a'+1;
a2[i].re=a[i].re*a[i].re;
a3[i].re=a[i].re*a2[i].re;
}
if (t[i]!='*')
{
b[i].re=t[i]-'a'+1;
b2[i].re=b[i].re*b[i].re;
b3[i].re=b[i].re*b2[i].re;
}
}

for (lim=0,L=1;L<=n;++lim,L<<=1);
for (i=1;i<L;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(lim-1));

fft(a,1);
fft(a2,1);
fft(a3,1);
fft(b,1);
fft(b2,1);
fft(b3,1);

for (i=0;i<L;++i)
{
c1[i]=a[i]*b3[i];
c2[i]=a2[i]*b2[i];
c3[i]=a3[i]*b[i];
}

fft(c1,-1);
fft(c2,-1);
fft(c3,-1);

for (i=m-1;i<n;++i)
{
if (c1[i].re-2*c2[i].re+c3[i].re<0.5)
{
ans.push_back(i-m+2);
}
}

printf("%d\n",int(ans.size()));
for (i=0;i<ans.size();++i) printf("%d ",ans[i]);

return 0;
}

void fft(cp* A,int type)
{
int i,j,k;
for (i=1;i<L;++i) if (i<r[i]) swap(A[i],A[r[i]]);
for (i=1;i<L;i<<=1)
{
cp w1(cos(PI/i),type*sin(PI/i));
for (j=0;j<L;j+=2*i)
{
cp w(1,0);
for (k=j;k<i+j;++k,w=w*w1)
{
cp t=A[k+i]*w;
A[k+i]=A[k]-t;
A[k]=A[k]+t;
}
}
}
if (type==-1) for (i=0;i<L;++i) A[i].re=A[i].re/L;
}