「学习笔记」FFT x 字符串匹配

使用 FFT 解决一系列字符串匹配问题。

设匹配函数 $C(x,y)$ 为字符 $x$ 和字符 $y$ 匹配的值，是我们自己定义的值。

两个字符串匹配的值就是对应位置上的字符匹配的值的和。

对于文本串 $S$ 和模式串 $T$，现在要求出 $T$ 在 $S$ 中所有匹配的位置。

为了化成卷积的形式，把 $T$ 反转。

这样 $T$ 和 $S$ 以 $i$ 为结尾的子串的匹配值为：

$$\sum_{j=0}^{|T|-1}C(S_{i-j},T_j)$$

为了能够区分不同位置的匹配值，定义生成函数：$P(x)$，$[x^i]$ 代表 $T$ 与 $S$ 以 $i$ 结尾的子串的匹配值。

那么：

$$P(x)=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}C(S_{i-j},T_j)$$

为了能通过观察匹配值来确定两个字符串，构造匹配函数 $C(x,y)=(x-y)^2$（字符的权值需满足两两不同，可以使用 ASCII 码来作为权值），则两个字符串匹配当且仅当匹配值为 $0$．

那么：

$$\begin{aligned} P(x)&=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}(S_{i-j}-T_j)^2 \\ &=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+{T_j}^2+S_{i-j}T_j \\ &=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{T_j}^2+\sum_{i=|T|-1}^{|S|}\sum_{j=0}^{|T|-1}S_{i-j}x^{i-j}T_jx^j \end{aligned}$$

另外，为了使得边界满足卷积的形式，对于”溢出”的部分定义其权值为 $0$，也就是我们需要计算：

$$\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{T_j}^2+\sum_{i=|T|-1}^{|S|}\sum_{j=0}^{i}S_{i-j}x^{i-j}T_jx^j$$

前两个柿子可以预处理前缀和来做到线性求出，后面是个卷积的形式，可以通过 FFT $\mathcal{O}(n\log n)$ 求出。

所以就可以 $\mathcal{O}(n\log n)$ 做到字符串匹配了。

栗题一 luoguP4173

带通配符的字符串匹配。

尝试构造匹配函数 $C(x,y)$ 满足：

• $x$ 或 $y$ 为通配符时值为 $0$；

• $x$ 和 $y$ 都不为通配符，且相同时值为 $0$；

• $x$ 和 $y$ 都不为通配符，且不相同时值 $>0$．

设通配符的权值为 $0$，$C(x,y)=(x-y)^2xy$．

$$\begin{aligned} P(x)&=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}(S_{i-j}-T_j)^2S_{i-j}T_j \\ &=S^3*T-2\times S^2*T^2+S*T^3 \end{aligned}$$

（这里的次方是点乘，$*$ 为卷积）

三次卷积，时间复杂度 $\mathcal{O}(n\log n)$．

栗题二 Codeforces 528 D

分别仅考虑 $A,C,G,T$，把匹配成功的位置取个交集就可以。

现在仅考虑 $A$，把 $S$ 中不会和 $A$ 匹配上的位置上的字符设为 $o$，把 $T$ 中不是 $A$ 的字符设为 #，则匹配函数 $C(x,y)$ （其中 $x$ 来自 $S$，$y$ 来自 $T$）要满足：

• $=0,x=A,y=A$；
• $=0,x=A,y=$ #；
• $>0,x=o,y=A$；
• $=0,x=o,y=$ #．

这样的 $C$ 才能满足匹配成功值为 $0$，否则大于 $0$．

设：

• $S$ 中的 $A$ 值为 $0$，$o$ 值为 $1$；

• $T$ 中的 $A$ 值为 $1$，# 值为 $0$；

• $C(x,y)=xy$．

对于每个字符只需要一次 FFT 就可以了。

Code