题解 P4173 【残缺的字符串】
Ebola
2018-08-05 09:17:31
这是一道通配符匹配模板题。对于通配符的匹配，本人发表拙作如下。
# 浅谈FFT在字符串匹配中的应用
### 背景引入
字符串匹配，是OI中的一个古老为传统的问题。常见的匹配问题有：单模式串匹配、多模式串匹配、字串匹配。而对应的算法是KMP、AC自动机、后缀自动机。而我们今天要谈的问题，是单模式串匹配问题的一种：带通配符的单模式串匹配。
为了逐步解决这个问题，我们从普通的单模式串匹配开始说起。
### 普通的单模式串匹配
问题概述：给定模式串A（长度为m）、文本串B（长度为n），需要求出所有位置p，满足B串从第p个字符开始的连续m个字符，与A串完全相同
KMP是这一类问题的优秀算法，理论复杂度是线性的。但今天我们要用FFT来解决这个问题。千万不要因为FFT的复杂度高于KMP而忽略这一段，因为这一段内容对接下来我们要解决的问题而言，非常重要。
为了使问题更便于研究，我们约定所有字符串的下标从0开始
我们定义字符串的匹配函数C(x,y)=A(x)-B(y)，那么我们可以形式化地定义“匹配”：若C(x,y)=0，则称A的第x个字符和B的第y个字符匹配。再定义完全匹配函数$P(x)=\sum\limits_{i=0}^{m-1}C(i,x-m+i+1)$，若P(x)=0，则称B以第x位结束的连续m位，与A完全匹配
但有没有觉得这个完全匹配函数有什么问题？似乎，根据完全匹配函数，“ab”与“ba”是匹配的？？？问题出在我们定义的匹配函数身上。匹配函数的确可以判断某一位是否匹配，但加了一个求和符号，一切都变了，只要两个串所含的字符是一样的，不管排列如何，完全匹配函数都会返回0值。
而这一切的罪魁祸首就是匹配函数的正负号！我们现在要做的是：定义一个更好的匹配函数，只要两个字符串某一位的匹配函数非零，完全匹配函数也不可能为零。不难想到给匹配函数加一个绝对值符号。但这样似乎就只能O(nm)暴力计算，没有更好的优化方法了。于是我们给匹配函数加上一个平方符号。此时完全匹配函数就是$P(x)=\sum\limits_{i=0}^{m-1}\left[A(i)-B(x-m+i+1)\right]^2$
这样还是没什么优化方法。我们不妨翻转A串，将翻转后的结果设为S。形式化地，S(x)=A(m-x-1)。据此不难推出A(x)-S(m-x-1)。于是完全匹配函数可以写成$P(x)=\sum\limits_{i=0}^{m-1}\left[S(m-i-1)-B(x-m+i+1)\right]^2$
大力展开这个函数：$P(x)=\sum\limits_{i=0}^{m-1}\left[S(m-i-1)^2+B(x-m+i+1)^2-2S(m-i-1)B(x-m+i+1)\right]$
再将求和符号拆开：$P(x)=\sum\limits_{i=0}^{m-1}S(m-i-1)^2+\sum\limits_{i=0}^{m-1}B(x-m+i+1)^2-2\sum\limits_{i=0}^{m-1}S(m-i-1)B(x-m+i+1)$
第一项是一个定值，可以O(m)预处理出来。第二项可以O(n)预处理前缀和。现在问题就在第三项。第三项中，两个小括号里面的东西加起来，似乎能抵消很多东西？居然……刚好等于x？这是巧合吗？~~当然不是，明明是我干出来的。~~所以，第三项是不是可以写成$-2\sum\limits_{i+j=x}S(i)B(j)$呢？当然可以！（这一步不太好解释，需要自己好好理解一下）
那么，我们设$T=\sum\limits_{i=0}^{m-1}S(i)^2\qquad f(x)=\sum\limits_{i=0}^xB(i)^2\qquad g(x)=\sum\limits_{i+j=x}S(i)B(j)$
于是就有$P(x)=T+f(x)-f(x-m)-2g(x)$
观察这个g函数，发现它不就是我们熟悉的卷积形式吗？而且还是最常规的卷积——多项式乘法！于是可以用FFT计算出g函数了！然后再代入计算一下，就可以O(n)得到所有P(x)的值了！
说了那么多，其实代码很短的。下面是核心代码。~~FFT相信大家都会，就不放出来了~~
```cpp
void FFT_Match(char *s1,char *s2,int m,int n)
{
for(int i=0;i<m;i++) A[i].r=s1[i]-'a'+1;
for(int i=0;i<n;i++) B[i].r=s2[i]-'a'+1;
reverse(A,A+m);double T=0;
for(int i=0;i<m;i++) T+=A[i].r*A[i].r;
f[0]=B[0].r*B[0].r;
for(int i=1;i<n;i++) f[i]=f[i-1]+B[i].r*B[i].r;
FFT(A,len,1);FFT(B,len,1);
for(int i=0;i<len;i++) g[i]=A[i]*B[i];
FFT(g,len,-1);
for(int x=m-1;x<n;x++)
{
double P=T+f[x]-f[x-m]-2*g[x].r;
if(fabs(P)<eps) printf("%d ",x-m+2);
}
}
```
### 带通配符的单模式串匹配
问题概述：给定模式串A（长度为m）、文本串B（长度为n），串的某些字符是“通配符”（通配符是一种可以与任意字符匹配的字符）。需要求出所有位置p，满足B串从第p个字符开始的连续m个字符，与A串完全相同
这个问题显然用KMP就无法解决了，我们还是考虑和上面类似的方法。那么我们回顾上面的普通串匹配过程，我们可以总结出思路大概是这样的：
1. 定义匹配函数
2. 定义完全匹配函数
3. 快速计算每一位的完全匹配函数值
有了通配符，我们肯定需要重新定义一个匹配函数
我们设通配符的数值为0，定义匹配函数$C(x,y)=[A(x)-B(y)]^2A(x)B(y)$，这样就完美地解决了通配符匹配问题。那么我们的完全匹配函数就是$P(x)=\sum\limits_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)$
还是老套路，将A串翻转，也就是设$S(i)=A(m-i-1)$
然后完全匹配函数变成：$P(x)=\sum\limits_{i=0}^{m-1}[S(m-i-1)-B(x-m+i+1)]^2S(m-i-1)B(x-m+i+1)$
暴力展开：$P(x)=\sum\limits_{i=0}^{m-1}S(m-i-1)^3B(x-m+i+1)+\sum\limits_{i=0}^{m-1}S(m-i-1)B(x-m+i+1)^3-2\sum\limits_{i=0}^{m-1}S(m-i-1)^2B(x-m+i+1)^2$
发现所有的项，都满足两个小括号加起来等于x，所以全部写成卷积的形式：
$P(x)=\sum\limits_{i+j=x}S(i)^3B(j)+\sum\limits_{i+j=x}S(i)B(j)^3-2\sum\limits_{i+j=x}S(i)^2B(j)^2$
这样只要做6次FFT外加1次IFFT就可以得到完全匹配函数每一位的值了
核心代码其实也不长，三次多项式乘法而已，常数略大
```cpp
void FFT_match(char *s1,char *s2,int m,int n)
{
reverse(ss1,ss1+m);
for(int i=0;i<m;i++) A[i]=(s1[i]!='*')?(s1[i]-'a'+1):0;
for(int i=0;i<n;i++) B[i]=(s2[i]!='*')?(s2[i]-'a'+1):0;
for(int i=0;i<len;i++) a[i]=Comp(A[i]*A[i]*A[i],0),b[i]=Comp(B[i],0);
FFT(a,len,1);FFT(b,len,1);
for(int i=0;i<len;i++) P[i]=P[i]+a[i]*b[i];
for(int i=0;i<len;i++) a[i]=Comp(A[i],0),b[i]=Comp(B[i]*B[i]*B[i],0);
FFT(a,len,1);FFT(b,len,1);
for(int i=0;i<len;i++) P[i]=P[i]+a[i]*b[i];
for(int i=0;i<len;i++) a[i]=Comp(A[i]*A[i],0),b[i]=Comp(B[i]*B[i],0);
FFT(a,len,1);FFT(b,len,1);
for(int i=0;i<len;i++) P[i]=P[i]-a[i]*b[i]*Comp(2,0);
FFT(P,len,-1);
for(int i=m-1;i<n;i++) if(fabs(P[i].r)<=1e-7) printf("%d ",i-m+2);
}
```
本题直接套用上述代码即可。